Diseño de Autómatas Finitos
1
Diseño de AFD’s
• Definir un AFD que acepte palabras que
cumplan ciertas especificaciones.
– Correcto: que las palabras aceptadas por el AFD cumplan
las especificaciones, es decir, que no “sobren” palabras.
– Completo: que toda palabra que cumpla las
especificaciones sea aceptada por el AFD, es decir, que no
“falten” palabras.
• Ejemplo: AFD que acepte palabras sobre {a, b} que no tengan
varias a’s seguidas.
El AFD de la figura no es
correcto porque acepta “baa”,
> q0
pero no acepta “ba”.
a
a
q1
b
b
a
q2
b
2
¿Cómo diseñar un autómata finito
• Por “ensayo y error” no es adecuado.
• “Póngase en los zapatos” del autómata que quiere
diseñar.
– Para cada símbolo leído, saber si la cadena es aceptada o no,
por si la cadena termina ahí.
– Decida que información es crucial “recordar”, es decir, cuales
serían los estados del autómata.
– Asignar transiciones, estado inicial y estado(s) final(es).
3
Ejemplo
• Diseñar un AFD que acepte todas las palabras sobre {0, 1} que
tengan un número impar de 1’s.
– No se requiere saber cuantos 1’s se han leído sino sólo si llevamos un número
par o impar de 1’s. Esta respuesta permanece igual si enseguida leemos un 0 y
cambia si leemos un 1.
– Representar esto como una lista de posibilidades y asignar un estado a cada
posibilidad: a) par hasta ahorita. B) impar hasta ahorita.
– Asignar las transiciones.
– Definir el estado inicial, el que corresponde a la palabra nula l.
– Definir el estado final, el que corresponde a palabras de longitud impar.
1
qpar
0
qimpar
1
0
4
Otro ejemplo
• Diseñar un AFD que reconozca palabras que contienen
la cadena 001 como 0010, 1001, 11111110011111, pero no
como 11, 0000, 1100, 10101.
Posibilidades:
–
–
–
–
No hemos leído ningún símbolo. Estado q.
Hemos leído un 0. Estado q0.
Hemos leído 00. Estado q00.
Hemos leído 001. Estado q001.
1
0,1
0
0
q
q0
0
q00
1
q001
1
5
Ejemplos
• Diseñar un AFD que acepte exactamente el
lenguaje sobre {0, 1} en que las palabras no
comienzan con 00.
0,1
q0
0
q1
0
q2
1
1
q3
0,1
6
Ejemplo
Palabras sobre {a, b, c} en las cuales toda b es
inmediatamente seguida de al menos una c.
a,c
a,c
b
q0
a,c
c
q1
a,b
b
q3
b
q0
q1
c
a,b
q2
q2
a,b,c
a,b,c
7
Otro ejemplo
• Construir un autómata finito determinista que reconozca el lenguaje
sobre {0, 1} que consiste de las palabras que terminan con ’10’, es
decir, reconoce el lenguaje (0 + 1)*10.
0
00
0
0
1
0
1
0
01
i
0 1
1
0
1
1
10
1
0
11
1
8
Simplificación del “Otro ejemplo”
0
A
1
1
B
0
1
C
0
9
Un ejemplo más
• Construir un autómata finito determinista que reconozca el lenguaje
sobre {0, 1} que consiste de las palabras que terminan con 1, es decir,
(0 + 1)*1.
0
1
1
A
0
B
10
Y un ejemplo más
• Construir un autómata finito determinsta que reconozca el lenguaje
sobre {0, 1} que consiste de las palabras cuyo penúltimo símbolo es 1,
es decir, su expresión regular es (0 + 1)*1(0 + 1).
0
0
C
0
1
A
1
0
B
1
D
1
11
Y aún otro más
•
Construir un autómata finito determinista que reconozca el lenguaje sobre {0,
1} que consiste de las palabras cuyo antepenúltimo símbolo es 1, es decir, su
expresión regular es (0 + 1)*1(0 + 1)(0 + 1).
0
E
1
C
0
0
1
0
A
1
0
B
F
1
1
0
D
1
0
G
0
1
H
1
12
Y varios más
• ¿Cuántos estados tendría el autómata finito determinista que reconozca el
lenguaje sobre {0, 1} que consiste de las palabras cuyo ante-antepenúltimo
símbolo es 1, es decir, su expresión regular es (0 + 1)*1(0 + 1)3?
– Resp: 24 = 16.
• ¿Cuántos estados tendría el autómata finito determinista que reconozca el
lenguaje sobre {0, 1} que consiste de las palabras cuyo décimo símbolo,
contado de derecha a izquierda es 1, es decir, su expresión regular es
(0 + 1)*1(0 + 1)9?
– Resp: 210 = 1024.
• ¿Cuántos estados tendría el autómata finito determinista que reconozca el
lenguaje sobre {0, 1} que consiste de las palabras cuyo vigésimo símbolo,
contado de derecha a izquierda es 1, es decir, su expresión regular es
(0 + 1)*1(0 + 1)19?
– Resp: 220 = 1M.
• ¿Cuántos estados tendría el autómata finito determinista que reconozca el
lenguaje sobre {0, 1} que consiste de las palabras cuyo vigésimo quinto
símbolo, contado de derecha a izquierda es 1, es decir, su expresión regular es
(0 + 1)*1(0 + 1)24?
– Resp: 225 = 32M.
13
Tarea 3, Parte A (en equipo)
• Construir un AFD que reconozca
números binarios múltiplos de 5.
– Por ejemplo, debe reconocer:
0, 101, 1010, 1111, 10100.
• Fecha de asignación: 19/Febrero/2004
• Fecha de entrega: 01/Marzo/2004
14
Equivalencia de autómatas finitos
• Decimos que dos autómatas, M1 y M2, son
equivalentes cuando aceptan el mismo lenguaje, es
decir, L(M1) = L(M2).
En este caso escribimos M1  M2.
• ¿Cómo saber que dos autómatas son equivalentes?
• ¿Cómo saber que dos autómatas no son
equivalentes?
15
¿Cuándo dos autómatas no son
equivalentes?
Cuando uno de los dos autómatas
acepta una palabra que no es
aceptada por el otro autómata,
podemos concluir que los dos
autómatas no son equivalentes
16
Ejemplo
a
q0
b
a
q1
b
a,b
a
q2
q0
M1
a,b
b
a
q1
b
q2
M2
¿Son M1 y M2 equivalentes? ¡No!
¿Por qué? Porque M1 acepta l y M2 no.
17
Ejemplo
0
0
q0
1
1
0
M1
0
q0
q1
1
1
0
q1
1
q2
M2
¿Son M1 y M2 equivalentes? ¡No!
¿Por qué? Porque M1 acepta 0 y M2 no.
Porque M2 acepta 01 y M1 no.
18
Ejemplo
0
0
q0
1
1
0
M1
0
q0
q1
1
1
0
q1
1
q2
M2
¿Son M1 y M2 equivalentes? ¡Sí!
¿Por qué? Porque todas las palabras que son
aceptadas por M1 también lo son
19
por M2 y viceversa.
¿TODAS las palabras?
• Para poder decir que dos autómatas son
equivalentes, debemos verificar que TODAS las
palabras aceptas por uno de los autómatas son
aceptadas por el otro y viceversa.
¿Cómo podemos verificar TODAS
las palabras?
¿Cómo podemos encontrar una
palabra que es aceptada por uno
de los autómatas pero no por el
otro?
20
¿Cómo saber que dos autómatas
son equivalentes
• Teorema de Moore. Existe un algoritmo basado en la
comparación de estados para saber si dos autómatas
son equivalentes.
• Definición. Dos estados son compatibles si ambos
son finales o ninguno de los dos lo es. Si uno es final
y el otro no lo es, entonces se dice que son
incompatibles.
21
Algoritmo de Moore
• Comparación de los autómatas M=(K, S, d, s0, F) y M’ = (K’, S, d’, s0’, F’).
Se construye la tabla de comparación con 1+|S| columnas. La primera columna
ponemos (q, q’) como encabezado. El encabezado de las columnas restantes son
los símbolos del alfabeto.
– 1) Inicialmente escribimos (s0, s0’) en el primer renglón de la primera columna.
– 2) Completamos el renglón poniendo en cada columna a la pareja de estados
donde el primer elemento de la pareja es el estado a donde se transfiere el
autómata M del estado en la primera columna después de leer el símbolo que
encabeza la columna correspondiente. El segundo elemento de la pareja es la
transición correspondiente a M’.
– 3) Cada pareja de estados generado en el punto 2) que no esté en la primera
columna se escribe en esa primera columna.
– 4) Se completa el renglón para la siguiente pareja de estados en la primera
columna.
– 5) Si en la primera columna aparece una pareja de estados incompatible,
entonces se termina el proceso y se concluye que los autómatas no son
equivalentes.
– 6) Si en la primera columna no aparecieron parejas de estados incompatibles y si
ya no aparecen nuevas parejas que no estén en la primera columna, entonces se
22
concluye el proceso y decimos que los autómatas son equivalentes.
Arbol de comparación
a
3
a
4
(1,3)
b
b
5
b
b
a
a
(2,4)
b
a
1
a
2
a
b
b
(1,5)
a
(2,5)
b
(1,4)
23
Determinar si los siguientes AFD’s son/no son equivalentes:
0
1
0
A:
1
2
0
0
B:
6
0
1
0
0,1
0
1
11
12
0
10
1
1
1
C:
5
0
1
9
4
8
7
1
3
1
1
0
0,1
1
13
0
14
1
0
1
16
0
15
18
0,1
0,1
1
17
0
24
Respuesta al ejercicio de la lámina anterior
• A y B sí son equivalentes.
• B y C no son equivalentes.
• A y C no son equivalentes.
25
Simplificación de autómatas
• Decimos que un autómata es una simplificación de otro
si tiene menos estados pero ambos aceptan el mismo
lenguaje.
• Decimos que en un AFD dos estados son equivalentes si
al tomar uno o el otro como estado inicial, los lenguajes
aceptados por los AFD’s resultantes son iguales. En otras
palabras, dado un AFD M = (K, S, d, s0, F) y dos estados
q0 y q1  K, decimos que q0 y q1 son equivalentes o
redundantes (q0  q1) si (K, S, d, q0, F)  (K, S, d, q1, F).
• Una vez que sabemos que dos estados son equivalentes,
entonces podemos eliminar uno de ellos. Pero, ¿y las
flechas que entran y salen del estado eliminado?
– Las flechas que salen del estado eliminado son eliminadas.
– Las flechas que entraban al estado eliminado se redirigen al
estado equivalente.
26
Estados equivalentes
a
b
5
3
(4’,3)
a
a
4
a
b
b
a
a
(3’,4)
b
b
(5’,5)
a, b
b
5’
3’
a
a
4’
b
b
27
Borrar transiciones
b
a
5
3
a
a
4
b
a
b
b
5
3
a
4
b
28
Redirigir transiciones
a
b
5
3
a
4
b
a
b
5
3
a
b
29
Obtención de AFD mínimo eliminando
estados equivalentes
• Teorema. Al eliminar estados redundantes de un
AFD se obtiene el único AFD mínimo que acepta
el mismo lenguaje que el original.
Algoritmo:
Para cada par de estados (p, q) del autómata
– Ver si son equivalentes.
– En caso de que sí, entonces eliminar uno de
ellos y volver a empezar con otros dos estados.
Hasta que no haya estados que eliminar.
30
Ejercicio.- simplificar:
0
0
0
8
7
0,1
1
0
6
0
1
11
1
1
9
0
10
12
1
1
31
Obtención de AFD mínimo utilizando
clases de equivalencia
Dado un AFD M = (K, S, d, s0, F), el procedimiento para
simplificarlo es:
• Definimos dos clases de equivalencia, F y K - F.
• Para cada clase
• Sea q un estado en la clase. Poner en una misma clase a
todos los estados q’ que tienen transiciones “iguales” a las
de q, es decir, q y q’ pertenecen a la misma clase si para
cada símbolo s  S, d(q’, s) “cae” en la misma clase que
d(q, s). Ponemos en otra clase a los que tienen transiciones
“distintas” a las de q.
• Si todos los estados de la clase tienen transiciones iguales,
entonces la clase no se divide y analizamos otra clase.
• Continuar analizando clases hasta que ninguna se divida.
32
Operaciones entre autómatas
• Sean
– M1 = (K1, S, d1, s1, F1) y
M2 = (K2, S, d2, s2, F2) dos AFDs que aceptan
los lenguajes L1 y L2, respectivamente.
• Cómo obtener autómatas que reconozcan
–
–
–
–
–
–
L1L2
L1L2
L1-L2
L1L2
L1*
L1C
33
Respuesta
• Definamos el autómata M = (K, S, d, s0, F) donde
–
–
–
–
K = K1 × K2
s0 = (s1, s2)
d((p, q), a) = (d1(p, a), d2(q, a)) para pK1, qK2 y aS
Si F = {(p, q) | pF1 o qF2}, entonces M acepta al
lenguaje L1L2.
– Si F = {(p, q) | pF1 y qF2}, entonces M acepta al
lenguaje L1L2.
– Si F = {(p, q) | pF1 y qF2}, entonces M acepta al
lenguaje L1-L2.
• ¿Y L1L2, L1*, L1C?
34
Ejemplo
• Consideremos los lenguajes sobre el alfabeto S={0, 1}:
– L1 = {x | 00 no es una subcadena de x}
– L2 = {x | x termina con 01}
1
0,1
0
A
1
L1
B
0
C
0
1
1
P
0
Q
0
R
1
L2
35
K1 × K2
1
1
BP
AP
CP
0
0
0
1
BQ
AQ
0
CQ
0
1
1
0
1
AR
BR
CR
36
L1  L2
1
1
AP
CP
0
0
0
BQ
1
0
CQ
0
1
1
0
1
AR
CR
37
L1  L2
1
1
AP
CP
0
0
0
BQ
1
0
CQ
0
1
1
0
1
AR
CR
38
L1 - L2
1
1
AP
CP
0
0
0
BQ
1
0
CQ
0
1
1
0
1
AR
CR
39
Ejercicio
• Ya que L1C = S*-L1, el AFD que acepta
L1C se obtiene:
– Cambiando los estados finales a no-finales y
los no-finales a finales.
1
0,1
0
A
1
B
0
1
0,1
C
0
L1
A
1
B
0
C
L1C
40
Obtenga un AF que acepte (11+110)*0
q1
1
r
1
t
1
0,1
q0
1
1
q0
u
s
0
1
0
0
0
q4
0
0,1
1
0
p
q2
1
q3
41
Autómatas Finitos No Deterministas
(AFN)
• En los Autómatas Finitos Deterministas, para
cada estado y símbolo existe uno y sólo un
estado al cual se hace la transición.
• ¿Y si se quita esta restricción? Es decir, si
estando en un estado, hay símbolos para los que
puede no existir transición o símbolos para los
que puede haber más de una.
• Este tipo de autómatas son llamados Autómatas
Finitos No Deterministas (AFN).
¿Cómo analizar los AFN’s?
42
Tarea 3, Parte B (en equipo)
• Ejercicios 3.10(a, b), 3.12, 3.19(b, e, h), 3.20(b,
d, f), 5.16(a, e, g) del texto.
– Fecha de asignación: 19/Febrero/2004
– Fecha de entrega: 01/Marzo/2004
43
Descargar

Diseño del Autómata Finito Determinístico