Download Gramatica y Automatas PDF

TitleGramatica y Automatas
File Size820.3 KB
Total Pages101
Table of Contents
                            NINGUNA ES EQUIVALENTE

2.5.5.1. De Moore a Mealy :
Ejemplo:
Definición:

Interpretación de funcionamiento:
Extensión a palabras
Aceptación de Palabras:
Lenguaje reconocido por un AFD:
Ejemplo:
Accesibilidad entre estados (A)
Conjunto Conexo
Equivalencias en los AFD
	Equivalencia entre AFD
Minimización de AFD
Configuración  instantánea y  movimiento
Implementación de un Algoritmo
Definición:

Interpretación de funcionamiento:
Extensión a palabras
Aceptación de Palabras:
Lenguaje reconocido por un AFD:
Ejemplo:
Accesibilidad entre estados (A)
Conjunto Conexo
Equivalencias en los AFD
	Equivalencia entre AFD
Minimización de AFD
Configuración  instantánea y  movimiento
Implementación de un Algoritmo

Autómatas Finitos No Deterministas (AFND)
	Conceptos asociados a los AFND
	Relaciones de Transiciones-λ   (Conjunto T).
	Cierre transitivo de la relación T  (Conjunto T*)
	Extensión a palabras
	Lenguaje Aceptado por un AFND
	Equivalencias entre AF  Determinista y No determinista
		Para el estado t  c0 :
		Para el estado s ε c0 :
	f1
	f2
P1
                        
Document Text Contents
Page 1

GRAMATICA

ALFABETO

Conjunto no vacío y finito de elementos, distintos entre sí e identificados, por ejemplo: números,
letras, combinaciones entre ellos.

Simbología:

Ejemplo: sea = y

“2 es un símbolo del alfabeto” se denota: 2 .

Otros ejemplos: =

= , el alfabeto de letras mayúsculas.

= , el alfabeto binario

Operaciones con Alfabetos

Los Alfabetos, en su condición de conjuntos, pueden ser sometidos a las operaciones
clásicas de la Teoría de Conjuntos, es decir Unión, Intersección, Diferencia y
Complementación de Conjuntos.

Las propiedades más importantes de dichas operaciones son:

Si =

Si =

( ) = ( )

( ) = ( )

( ) = ( ) ( )

( ) = ( ) ( )

= y =

Potencia de un alfabeto

Si es un alfabeto, es posible expresar el conjunto de todas las cadenas de cierta longitud de

dicho alfabeto utilizando una notación exponencial. Definimos como .

Como el conjunto de cadenas de longitud k, tales que todos los símbolos que las forman

pertenecen a .

Ejemplo: Si = , entonces = ; = ;

http://www.profesores.frc.utn.edu.ar/sistemas/ssl/Marciszack/GHD/Concepto2.htm

Page 2

=

Nótese además que independiente, de cual sea el alfabeto siempre = , siendo la
única cadena cuya longitud es 0.

Otra cuestión que se presta a confusión es la diferencia que existe entre = , y =

, donde la primera es un alfabeto con símbolos cero y uno y el segundo es un conjunto
de cadenas de longitud unitaria.

PALABRA

Se llama Palabra, Cadena o Tira a la concatenación o secuencia finita de elementos de
un alfabeto.

Simbología: Las palabras se denotan con las últimas letras del alfabeto en minúscula (x
= “001” , y = “ai”)

Ejemplo:

Longitud de una palabra.

Cada palabra tiene su longitud, es decir, el número o la cantidad de elementos que la
componen.

Simbología: (se utilizan dos barras a los costados de la palabra)

Ejemplo: sean las palabras: x = “001”, y = “ai”, z = “ZXABK”

= 3 = 2 = 5

La longitud de una palabra o cadena puede asumir distintos valores, si la longitud es
igual a 1, la palabra es igual al elemento o símbolo del alfabeto, es decir, que cada elemento o
símbolo de un alfabeto puede ser una tira o cadena del mismo.

Ejemplo: “0”

“A”

Palabra Vacía.

Si la longitud de una palabra es igual a 0, estamos frente a una palabra que existe pero
que no contiene elementos, llamada “palabra vacía” y es una cadena sobre cualquier alfabeto.

Simbología: = 0

Subpalabras: Prefijo y Sufijo.

Page 50

Q/E2 = [{ r } , { t } , { q }, {p , s }]

Vemos ahora que: Q/E1 = Q/E2, por lo tanto el proceso se detiene, y las clases de
equivalencias resultan:

Q/E = [{ r } , { t } , { q }, {p , s }]

Denominaremos con d1 = {r} ; d2 = {t} ; d3 = {q} ; d4 = {p,s} a los estados, y el
nuevo autómata nos quedará:

AFD3 ´= ( { a , b }, { d1, d2 , d3, d4 }, d4, {d1, d2}, f ) , donde:

f a b

d1 d4 d4

d2 d1 d4

d3 d2 d4

d4 d4 d2

Minimización de AFD

El objetivo de minimización de los AFD, es obtener un autómata equivalente al dado, o
sea que aceptará el mismo lenguaje, pero este nuevo autómata contendrá un menor número
de estados.

Los pasos a realizar para la obtención del autómata mínimo son los siguientes:

· Se debe encontrar el autómata conexo, para estos el autómata debe
cumplir que todos sus estados sean accesibles desde el estado inicial. Si
existiera algún estado que no cumpliera con esta condición se lo podrá
eliminar, sin que se afecte el lenguaje aceptado por el autómata.

· Determinar el Conjunto cociente, en el cuál nos indicará el mínimo número
de estados con diferente significado.

· Construir el nuevo autómata, para ello se utilizarán los estados
determinados por las clases de equivalencia. El estado inicial del nuevo
autómata, pertenecerá a la clase de equivalencia en donde se encuentre el
estado inicial del autómata original, y los mismo ocurrirá con los estados
finales de aceptación, en donde serán los que pertenezcan a clases de
equivalencias donde se encuentren estados finales de aceptación del
autómata original. Con respecto a las transiciones de los nuevos estados,
estas se realizarán en función a las transiciones de los estados que
conforman la clase de equivalencia respectiva.

Ejemplo:
Dado el siguiente AFD definido como:

AFD4 = ( ∑, Q, qi, F, f ), donde:

∑= { a , b }

Page 51

Q= { p, q, r , t, s }

qi = p

F= {q , r }

Donde la función f será:

f a b

p s r

* q t p

* r p s

s p r

t t q

Se pide :

a) Grafo

b) Autómata conexo

c) Conjunto Cociente

d) Autómata mínimo

e) Grafo del nuevo autómata

f) Identificar una cadena de longitud 5 y verificar que la misma es aceptada
por ambos autómatas

Resolución:

a) Grafo del Autómata

Similer Documents