View
16
Download
0
Category
Preview:
Citation preview
Autómatas finitos deterministas
Dr. Julio J. Águila G.
22 de agosto de 2004
Última revisión: 29 de agosto de 2019
29/08/2019 Autómatas finitos deterministas 2
Contenidos
Autómatas finitos deterministas.
Conversión desde AFN hacia AFD.
29/08/2019 Autómatas finitos deterministas 3
Definición AFD
Un autómata finito determinista ( AFD) es un caso especial de un autómata finito no determinista, en el cual:
1. Ningún estado tiene una transición vacía.
2. Para cada estado s y cada símbolo de entrada a, hay a lo sumo una arista etiquetada a que sale de s.
29/08/2019 Autómatas finitos deterministas 4
Autómata
AUTÓMATA
reconocedor
de un
lenguaje:
¿pertenece la
palabra al
lenguaje?
palabra
de
entrada
Solo hay dos
respuestas
posibles: SÍ o
NO
29/08/2019 Autómatas finitos deterministas 5
Algoritmo de reconocimiento estado= s0
carácter_de_entrada= yylex()
mientras carácter_de_entrada ≠ EOF hacer
estado= mueve( carácter_de_entrada, estado)
carácter_de_entrada= yylex()
fin mientras
si estado ∈ F entonces
regresar “Sí pertenece”
sino
regresar “No pertenece”
fin si
29/08/2019 Autómatas finitos deterministas 6
Ejemplo AFD (a|b)*abb
Sea entonces M un AFD, tal que M= { S, Σ, Δ, s0, F} donde:
S= { 0, 1, 2, 3}
Σ= { a, b}
Δ= { { 0, a, 1}, { 0, b, 0}, { 1, a, 1}, { 1, b, 2}, { 2, a, 1}, { 2, b, 3}, {3, a, 1}, { 3, b, 0}}
s0= {0}
F= {3}
29/08/2019 Autómatas finitos deterministas 7
Diferencia con AFN (a|b)*abb
Sea entonces M un AFN, tal que M = {S, Σ, Δ, s0, F} donde:
S= { 0, 1, 2, 3}
Σ= { a, b}
Δ= { { 0, a, {0,1}}, { 0, b, {0}}, {1, b, {2}}, { 2, b, {3}}}
s0= {0}
F= {3}
29/08/2019 Autómatas finitos deterministas 8
Ejemplo AFD (a|b)*abb
a
Inicio
2 a b
1 0 3
a
b b
b
a
29/08/2019 Autómatas finitos deterministas 9
Diferencia con AFN (a|b)*abb
0 1 2 3 Inicio
a
a
b
b b
29/08/2019 Autómatas finitos deterministas 10
Diferencia con AFN (a|b)*abb
Inicio
2
a
3
4
b
5
6 1
7 0
8 10 9
a b b
29/08/2019 Autómatas finitos deterministas 11
Tabla de Transiciones (a|b)*abb
E s ta d o s a b
0 1 0
1 1 2
2 1 3
3 1 0
29/08/2019 Autómatas finitos deterministas 12
Diferencia Tabla de Transiciones (a|b)*abb
Estado
Símbolo de Entrada
a
b
0
{0,1}
{0}
1
-
{2}
2
-
{3}
29/08/2019 Autómatas finitos deterministas 13
Movimientos del AFD
a a b b
0 -> 1 -> 1 -> 2 -> 3
a a b a
0 -> 1 -> 1 -> 2 -> 1
No existen más caminos para las cadenas
29/08/2019 Autómatas finitos deterministas 14
Diferencia Movimientos del AFN
a a b b
0 -> 0 -> 1 -> 2 -> 3
a a b a
0 -> 0 -> 0 -> 0 -> 0
a a b b
0 -> 0 -> 0 -> 0 -> 0
29/08/2019 Autómatas finitos deterministas 15
Implementación
Está claro que la construcción de un AFN es más sencilla y directa que la de un AFD, sin embargo la implementación en un programa de computador podría resultar en una simulación bastante dificultosa debido al hecho de que en la mayoría de los casos se debería probar todos los caminos antes de decidir si una cadena pertenece o no al lenguaje.
Por lo tanto, mediante un método denominado construcción de subconjuntos de Thompson, convertimos un AFN en AFD y así podemos aplicar el algoritmo que se mostró al principio del capítulo.
29/08/2019 Autómatas finitos deterministas 16
Conversión de un AFN en AFD
Construcción de subconjuntos de Thompson
Informalmente el proceso de transformación de un AFN en AFD se puede describir de la siguiente forma:
Paso 1:
Se calcula el conjunto cerradura-ε( s0), i.e. el conjunto de todos los estados posibles que son alcanzables solo con transiciones ε desde el estado s0, incluido el mismo.
29/08/2019 Autómatas finitos deterministas 17
cerradura- ε({0}) = {0, 1, 2, 4, 7}
Inicio
2
a
3
4
b
5
6 1
7 0
8 10 9
a b b
29/08/2019 Autómatas finitos deterministas 18
Paso 2:
Se calcula el conjunto cerradura- ε( mueve( A, a)) donde A representa el conjunto creado en el paso 1, a representa cada letra del alfabeto y mueve( A, a) es el conjunto de estados que se pueden alcanzar desde A con a.
29/08/2019 Autómatas finitos deterministas 19
mueve( { 0, 1, 2, 4, 7}, a)) = { 3, 8}
Inicio
2
a
3
4
b
5
6 1
7 0
8 10 9
a b b
29/08/2019 Autómatas finitos deterministas 20
cerradura- ε({3, 8}) = {1, 2, 3, 4, 6, 7, 8}
Inicio
2
a
3
4
b
5
6 1
7 0
8 10 9
a b b
29/08/2019 Autómatas finitos deterministas 21
Paso 3: el paso 2 se repite hasta que no puedan crearse nuevos conjuntos.
a b
{0 , 1 , 2 , 4 , 7 } {1 , 2 , 3 , 4 , 6 , 7 , 8 } {1 , 2 , 4 , 5 , 6 , 7 }
{1 , 2 , 3 , 4 , 6 , 7 , 8 } {1 , 2 , 3 , 4 , 6 , 7 , 8 } {1 , 2 , 4 , 5 , 6 , 7 , 9 }
{1 , 2 , 4 , 5 , 6 , 7 } {1 , 2 , 3 , 4 , 6 , 7 , 8 } {1 , 2 , 4 , 5 , 6 , 7 }
{1 , 2 , 4 , 5 , 6 , 7 , 9 } {1 , 2 , 3 , 4 , 6 , 7 , 8 } {1 , 2 , 4 , 5 , 6 , 7 , 1 0 }
{1 , 2 , 4 , 5 , 6 , 7 , 1 0 } {1 , 2 , 3 , 4 , 6 , 7 , 8 } {1 , 2 , 4 , 5 , 6 , 7 }
29/08/2019 Autómatas finitos deterministas 22
Los conjuntos creados representan los estados del AFD. Aquellos conjuntos que contengan estados finales del AFN se consideran finales para el AFD.
a b
A B C
B B D
C B C
D B E
E B C
29/08/2019 Autómatas finitos deterministas 23
AFD de (a|b)*abb
a
Inicio
D a b B A E
a
b
b
b
a
C
a
b
29/08/2019 Autómatas finitos deterministas 24
Minimización del número de estados
a b
A B C
B B D
C B C
D B E
E B C
29/08/2019 Autómatas finitos deterministas 25
Resultado de la minimización
a b
A B A
B B D
D B E
E B A
29/08/2019 Autómatas finitos deterministas 26
AFD (a|b)*abb
a
Inicio
D a b
B A E
a
b b
b
a
29/08/2019 Autómatas finitos deterministas 27
Minimizando el AFN
Inicio
2
a
3
4
b
5
6 1
7 0
8 10 9
a b b
29/08/2019 Autómatas finitos deterministas 28
AFN sin transiciones vacías
0 1 2 3 Inicio
a
a
b
b b
29/08/2019 Autómatas finitos deterministas 29
Aplicando la transformación
a b
A = {0 } {0 , 1 } = B {0 } = A
B = {0 , 1 } {0 , 1 } = B {0 , 2 } = C
C = {0 , 2 } {0 , 1 } = B {0 , 3 } = D
D = {0 , 3 } {0 , 1 } = B {0 } = A
29/08/2019 Autómatas finitos deterministas 30
AFD (a|b)*abb
a
Inicio
C a b
B A D
a
b b
b
a
Recommended