Clase 15 - AFD Resumido V2

Vista previa del material en texto

ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
AUTÓMATA FINITO (AF):
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
Para presentar el modelo AF, recordemos el ejemplo de MEF tipo Moore, 
visto anteriormente: 
MEF Moore
En este tipo de MEF los estados tienen asociados un 
símbolo de salida, en este caso el modelo reconoce 
palabras del Lenguaje Regular cuya Expresión Regular 
es: (b*.a)*.b.b*. Para lo cual necesariamente debe 
comenzar por el estado “q0” y al terminar de leer la 
secuencia de entrada, la misma se acepta si la última 
salida fue “A” o sea cuando termina en “q1” y se rechaza 
si fue “R” o sea si termina en “q0”. 
Vamos a generalizar este caso especial de MEF tipo 
Moore, considerando las salidas en forma implícita y 
diciendo que el estado “q1” es un estado de Aceptación 
o FINAL y que “q0” es un estado de Rechazo o NO-
FINAL; además “q0” tiene el rol de estado INICIAL.
AF
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
AUTÓMATA FINITO (AF):
Entonces definiremos al AF como una MEF 
tipo Moore especial, que a la vez es un caso 
particular del modelo más general: la MT. 
Para comprenderlo mejor lo representare-
mos con el siguiente esquema:
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
Al comienzo se escribe en la cinta de entrada la palabra que se desea analizar (ei ), la misma termina con 
un símbolo de fin de cadena que por simplicidad no consideraremos en forma explícita y un cabezal de 
lectura se encuentra sobre la posición del primer símbolo de dicha palabra. Esta descripción corresponde 
al ESTADO INICIAL del AF y desde aquí el modelo comienza a funcionar del siguiente modo:
1)LEE un símbolo de la cinta de entrada y mueve el cabezal a la derecha.
2)De acuerdo al ESTADO ACTUAL y al símbolo leído, transiciona a un NUEVO ESTADO (que puede ser 
el mismo).
3)Repite 1) y 2) hasta que lee totalmente la palabra, en este caso si se encuentra en alguno de los llamados 
ESTADOS FINALES se dice que la palabra escrita inicialmente es ACEPTADA y en caso contrario es 
RECHAZADA; o hasta que se llega a un estado en el que no está definida una transición, entonces se 
dice que el AF se BLOQUEA y la secuencia de entrada es RECHAZADA.
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
AUTÓMATA FINITO (AF):
Definición formal de un Autómata Finito:
AF =  Q , Σ , q0 , F , f 
Q : Conjunto finito y no vacío de estados.
Σ : Alfabeto de símbolos de entrada.
q0 : Estado inicial (perteneciente a Q).
F : Conjunto de estados finales (incluido en Q).
f : Función de control o transición, que se define como:
f : Q x   Q 
El criterio de aceptación está dado por la doble condición de llegar a la 
lectura del último símbolo de entrada y transicionar a un estado Final.
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
AF =  Q , Σ , q0 , F , f 
Q = { 1, 2 } 
 = { a, b } 
q0 = 1 F = { 2 } 
Este AF acepta el lenguaje L(AF) = { an bm / n  0 , m  1 } sobre el 
alfabeto {a, b}, que contiene todas las palabras compuestas por una 
secuencia de “a” seguida de otra secuencia de “b” o solamente una 
secuencia de “b”.
EJEMPLO DE AF:
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
TABLA DE TRANSICIÓN
Estado 
Actual
Símbolo
Leído
Estado 
Nuevo
→ 1 a 1
1 b 2
* 2 b 2
GRAFO DE TRANSICIÓN
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
AUTÓMATAS FINITOS DETERMINISTAS (AFD):
AUTÓMATA CONEXO: Un AFD se dice 
conexo cuando todos sus estados son 
accesibles desde el estado inicial.
AUTÓMATA COMPLETO: Un AFD se 
dice completo cuando todos sus estados 
tienen transiciones con cada uno de los 
símbolos de entrada válidos.
ESTADO SUMIDERO: Un estado se llama 
sumidero cuando no es final y transiciona 
con todos los símbolos de entrada a si 
mismo. Es un estado de rechazo.
ESTADO GENERADOR: Un estado es 
generador cuando solo salen transiciones 
desde él. Solo es útil cuando es el inicial.
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
ING. JORGE BUABUD
En general la función de transición de los 
AF, representa la relación entre:
• Par estímulo (estado actual, símbolo leído)
• La reacción (estado nuevo)
Esta relación en general puede ser:
• Determinista: cuando para un estímulo 
hay una sola reacción.
• No-determinista: cuando para un 
estímulo puede haber varias reacciones 
posibles.
En el caso de los AF, se puede afirmar que 
son DETERMINISTAS por naturaleza. 
Esto quiere decir que para todo AF No-
determinista existe un equivalente 
Determinista.
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
AUTÓMATAS FINITOS DETERMINISTAS (AFD):
EJEMPLOS DE AFD:
1 2
4
3
5
a
a
b
b
a
a
b
Características:
✓ Conexo
✓ Incompleto
✓ Estado 1 generador 
1
4
32
7
5
b
b
b
a
a
ba
a b
a
Características:
✓ No-conexo
✓ Completo
✓ Estado 5 generador 
✓ Estado 6 sumidero
6
b,a
a
bAFD1
AFD2
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
ING. JORGE BUABUD
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
AUTÓMATAS FINITOS DETERMINISTAS (AFD):
EJEMPLOS DE AFD:
1 2
4
3
5
a
a
b
b
a
a
Características:
✓ Conexo
✓ Completo
✓ Estado 4 sumidero
b
b
a,b
AFD3
Características:
✓ Conexo
✓ Completo
✓ Estado 1 generador 
✓ Estado 4 sumidero
b
1
4
32
6
5
b
b,a
a
b
a
a b
a
a
b
AFD4
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
ING. JORGE BUABUD
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
AUTÓMATAS FINITOS DETERMINISTAS (AFD):
REPRESENTACIÓN MATRICIAL:
Cuando tenemos un AF completo conviene representar su función de 
transición con una matriz cuyas columnas representan los símbolos de 
entrada y sus filas los estados.
AFD4 a b
→1 4 2
*2 3 2
3 4 6
4 4 4
*5 4 3
*6 6 5
AFD2 a b
→1 1 2
*2 7 2
3 2 7
4 3 4
*5 4 7
6 6 6
*7 6 7
AFD3 a b
→1 2 1
2 3 4
3 5 1
4 4 4
*5 2 4
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
ING. JORGE BUABUD
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
AUTÓMATAS FINITOS DETERMINISTAS (AFD):
¿ CÓMO HACEMOS CONEXO A UN AF ? :
Simplemente se elimina los estados inaccesibles y todas las transiciones que 
salen o llegan a ellos. Hay una correspondencia entre estos estados y los 
No-terminales inútiles de una GR. 
Por ejemplo, el AFD2 quedaría:
AFD2 a b
→1 1 2
*2 7 2
6 6 6
*7 6 7
b
1
2
7
b
a
6
b,a
a
b
a
AFD2
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
ING. JORGE BUABUD
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
AUTÓMATAS FINITOS DETERMINISTAS (AFD):
¿ CÓMO COMPLETAMOS UN AF ? :
Si el AF tiene un estado sumidero o algún estado sin transiciones, enviamos 
todas las transiciones faltantes hacia ese estado. Caso contrario 
agregamos un estado sumidero nuevo y procedemos igual.
Por ejemplo, el AFD1 quedaría: 
1
2
4
3
5
a a
b
b
a
a
b
AFD1
6
b
a
ba,b
AFD1 a b
→1 2 6
2 3 4
3 5 3
4 6 5
*5 2 6
6 6 6
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
ING. JORGE BUABUD
ING. JORGE BUABUD
LENGUAJES REGULARES Y 
AUTÓMATAS FINITOS
U.T.N. – F.R.T. 
S. y S. de los L.
AUTÓMATAS FINITOS DETERMINISTAS (AFD):
Ejemplos de AFD y sus ER correspondientes:
Lenguaje sobre ={a,b,c} de secuencias de
“a,b” con prefijo “a,b,c” y con sufijo “c”
más secuencias de “a”:
ER = (a+b+c).(a+b)*.c.a*
AFD5
2 3
a, b, c c
1
a, b a
4a, b, c
b, c
Lenguaje sobre ={a,b} de secuencias
de “a” con prefijo “ab” y sufijo “ba”:
ER = a.b.a*.b.a
AFD6
31
2
a b a
b
a, b
4
5
6
a
b
a
a
a, b
b
ING. JORGE BUABUD
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
AUTÓMATAS FINITOS DETERMINISTAS (AFD):
Ejemplos de AFD y sus ER correspondientes:
Lenguaje de secuencias pares y 
sobre ={a, b, c}:
ER = ((a+b+c).(a+b+c))*
AFD7
2 31
a, b, c
a, b, c
a, b, c
Lenguaje de secuencias con prefijo 
“a” y sufijo “b” sobre ={a, b}:
ER = a.(a+b)*.b
AFD8
a
2 41
3
a bb
a
b
a,b
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
ING. JORGE BUABUD
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
AUTÓMATAS FINITOS DETERMINISTAS (AFD):
Otros ejemplos de AFD
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
ING. JORGE BUABUD
AFD10 AFD11 AFD12
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
EQUIVALENCIA Y MINIMIZACIÓN:
EQUIVALENCIA DE DOS AFD:
Dados los AFD A1 y A2 se dice 
que son equivalentes si y solo si 
los lenguajes que aceptan son 
iguales: A1A2  L(A1)=L(A2)
MINIMIZACIÓN DE UN AFD:
De todos los equivalentes de un 
AFD A, el AFD MÍNIMO 
correspondiente a A es aquel que 
tiene la menor cantidad de estados. 
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
ING. JORGE BUABUD
EXTENSIÓN DE LA FUNCIÓN DE TRANSICIÓN:
Con el objetivo de representar formalmente el lenguaje aceptado por un AFD y poder 
definir algunos conceptos necesarios para la Minimización y verificación de 
Equivalencia; vamos a generalizar la función f de un AFD para que trabaje con 
palabras del universo de entrada, denominándola f’ ´quedaría de la siguiente forma: 
f’: Q x *  Q ; incluido el caso particular f’(q, ) = q, es decir que para la palabra 
vacía no se transiciona, permaneciendo en el mismo estado.
U.T.N. – F.R.T. 
S. y S. de los L.
EQUIVALENCIA Y MINIMIZACIÓN:
LENGUAJE ACEPTADO POR UN AFD: Conjunto de todas las 
palabras del universo del alfabeto de entrada que hagan transicionar al 
AFD desde su estado inicial a algún estado final. 
L(AFD) = {w / w* y f’(q0, w)F}
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
EQUIVALENCIA ENTRE DOS ESTADOS DE UN AFD:
Dos estados q1 y q2  Q de un AFD, se dicen equivalentes: 
q1q2 si y solo si  w*, f’(q1,w)F  f’(q2,w)F
Se dice que q1 y q2 tienen el mismo “comportamiento” para todas las 
palabras w, es decir que para las mismas secuencias transicionan al 
mismo tipo de estado, ya sea final o no-final.
ING. JORGE BUABUD
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
EQUIVALENCIA Y MINIMIZACIÓN:
EQUIVALENCIA DE ORDEN N: Con el objetivo de definir un algoritmo para 
obtener los subconjuntos de estados equivalentes de un conjunto de estados dado, 
vamos a definir el concepto de Equivalencia de Orden N entre dos estados:
q1 N q2 si y solo si  w*  |w|  N, f’(q1,w)F  f’(q2,w)F
Es decir que los estados N-equivalentes tienen el mismo “comportamiento” para todas las 
secuencias de longitud menor o igual que N.
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
RELACIÓN ENTRE EQUIVALENCIA Y N-EQUIVALENCIA: 
Dado un AFD con K estados, podemos afirmar que dos estados son equivalentes si se 
verifica que son N-equivalentes para N=K-2. Esto se puede demostrar realizando 
divisiones sucesivas del conjunto de todos los estados en cuestión, separando los 
estados N-equivalentes, desde N=0 y mientras se pueda seguir dividiendo. El límite 
será la cantidad K de estados menos uno, por ende se podrá llegar a lo sumo hasta 
N=K-2. Este proceso se conoce como particiones del conjunto Q. 
ING. JORGE BUABUD
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
EQUIVALENCIA Y MINIMIZACIÓN:
CLASES DE EQUIVALENCIA DE UN CONJUNTO DE ESTADOS:
Dado un conjunto de estados de un AFD o la unión de los conjuntos de estados de 
dos o más AFD, se llama Clases de Equivalencia a los subconjuntos de estados 
equivalentes. También se hace extensible al concepto de N-equivalencia.
CONJUNTO COCIENTE DE UN CONJUNTO DE ESTADOS:
Dado un conjunto de estados de un AFD o la unión de los conjuntos de estados de 
dos o más AFD, se llama Conjunto Cociente al conjunto de todas las Clases de 
Equivalencia del conjunto de estados en cuestión.
PARTICIÓN N DE UN CONJUNTO DE ESTADOS:
Dado un conjunto de estados de un AFD o la unión de los conjuntos de estados de 
dos o más AFD, se llama Partición N al conjunto de todas las Clases de 
N-equivalencia del conjunto de estados en cuestión.
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
ING. JORGE BUABUD
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
EQUIVALENCIA Y MINIMIZACIÓN:
ALGORITMO PARA OBTENER EL CONJUNTO COCIENTE:
Entrada: AFD A= Q, , q0, F, f  Salida: Conjunto Cociente QE
Obtener la partición de 0-equivalencia: P0={ F , ~F }
Asignar i=-1
Repetir
Asignar i=i+1
Para cada p,qCk {Ck=Clases de Equivalencia de Pi o sea Ck Pi}
Si p i q   x , ( f(p,x)Ck  f(q,x)Ck )
entonces p i+1 q {o sea que siguen juntos en Pi+1}
sino p i+1 q {o sea que se separan en Pi+1}
Hasta que Pi+1=Pi
Asignar QE=Pi
/
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
ING. JORGE BUABUD
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
EQUIVALENCIA Y MINIMIZACIÓN:
MINIMIZACIÓN DE UN AFD:
Para obtener el Mínimo de un AFD A dado, se debe obtener el conjunto cociente 
del mismo y luego tomar como estados a las clases de equivalencias. 
Formalmente debemos seguir los siguientes pasos:
1) Encontrar el AFD completo y conexo de A =  Q ,  , q0 , F, f 
2) Construir el conjunto cociente QE correspondiente.
3) El AFD Mínimo AMIN =  QMIN ,  , qMIN0 , FMIN , fMIN 
queda definido de la siguiente forma:
QMIN = QE
qMIN0 = Ck tal que CkQE  q0Ck
FMIN = {Ck / CkQE  CkF  } 
fMIN(Cn , x) = Cm tal que f(q,x)=p con qCn  pCm
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
ING. JORGE BUABUD
ING. JORGE BUABUD
LENGUAJES REGULARES Y 
AUTÓMATAS FINITOS
U.T.N. – F.R.T. 
S. y S. de los L.
EQUIVALENCIA Y MINIMIZACIÓN:
EJEMPLO DE OBTENCIÓN DE AFD MÍNIMO:
Consideremos el AFD12 y apliquemos el algoritmo de minimización:
1) Se trata de un AFD conexo y completo. 3) Planteamos el AFD-Mín
2) Obtenemos el Conjunto Cociente:
P0 = { [4 , 5 , 6] , [1 , 2 , 3] }
P1 = { [4] , [5 , 6] , [1 , 2 , 3] }
P2 = { [4] , [5 , 6] , [1] , [2 , 3] }
C1 C2
C2
C1
C1
C1
C1
C1
C2
C1
C2
C1
C2
C1
AFD12-Mín
a b
*C1 C4 C2
*C2 C2 C2
→C3 C4 C1
C4 C4 C2
ING. JORGE BUABUD
C1 C2 C3
C3
C2
C2
C2
C2
C2
C3
C1
C3
C2
C3
C2
C1 C2 C3 C4
C4
C2
C2
C2
C2
C2
C4
C1
C4
C2
C4
C2
P3 = P2
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
EQUIVALENCIA Y MINIMIZACIÓN:
EQUIVALENCIA DE AFD POR ISOMORFISMO:
Sean A1= Σ , Q1 , q10 , F1 , f1  y A2= Σ , Q2 , q20 , F2 , f2 , con |Q1|=|Q2|
Se dice que A1 y A2 son isomorfos, si existe una función biyectiva 
ß : Q1 → Q2 que cumple:
1) ß(q10) = q20, es decir, los estados iniciales son correspondientes
2) q ∈ F1 ⇔ ß(q) ∈ F2 es decir, los estados finales son correspondientes
3) ß(f1(q , a)) = f2(ß(q) , a) ∀ a ∈ Σ y q ∈ Q1
En definitiva, a cada estado le corresponde otro equivalente que solo se 
diferencia en el nombre. 
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
ING. JORGE BUABUD
Podemos afirmar que dos AFD Isomorfos son Equivalentes
ING. JORGE BUABUD
LENGUAJES REGULARES Y 
AUTÓMATAS FINITOS
U.T.N. – F.R.T. 
S. y S. de los L.
EQUIVALENCIA Y MINIMIZACIÓN:
VERIFICACIÓN DE EQUIVALENCIA POR ISOMORFISMO:
Consideremos los autómatas AFD10 y AFD11, una forma de verificar la 
equivalencia es en primer lugar minimizarlos y luego por simple 
comparación verificar si son Isomorfos. 
Vemos que en este caso se cumple el isomorfismo y por lo tanto 
concluimos que son equivalentes.
ING. JORGE BUABUD
AFD10-Mín AFD11-Mín