Autómatas Finitos

por Eduardo Virueña Silva

AFD mínimo

Línea 1: f(q0, 0) f(q0, 1) [final(q0)]
Línea 2: f(q1, 0) f(q1, 1) [final(q1)]
...
Línea N: f(qN, 0) f(qN, 1) [final(qN)]
Línea en blanco.

final(qk) = '*', si qk es estado final.
final(qk) = ' ', si qk no es estado final
ejemplo

AFD mínimo

AFD Producto

Primer autómata
Línea 1: f(q0, 0) f(q0, 1) [final(q0)]
Línea 2: f(q1, 0) f(q1, 1) [final(q1)]
...
Línea en blanco

Segundo autómata
Línea 1: f(q0, 0) f(q0, 1) [final(q0)]
Línea 2: f(q1, 0) f(q1, 1) [final(q1)]
...
Línea en blanco

Función booleana


final(qk) = '*', si qk es estado final.
final(qk) = ' ', si qk no es estado final

La función booleana se escribe con cuatro bits.
Por ejemplo:
0001 es AND (autómata intersección)
0111 es OR (autómata unión)
0110 es XOR (autómata diferencia simétrica)
1001 es IFF (autómata equivalencia)
ejemplo

AFD producto

Expresión regular a AFD

Las expresiones regulares se escriben así:
ER::= term { + term }
term::= factor { factor }
factor::= prim {*}
prim:= empty | lambda | 0 | 1 | (ER)
Ejemplo:
00+11*
(0+1)*
lambda + 00*
(empty)* (00* + 11*)(0101)

Expresión Regular a AFD

AFD a expresión regular

Línea 1: Número de estados
Línea 2: f(q0, 0) f(q0, 1) [final(q0)]
Línea 3: f(q1, 0) f(q1, 1) [final(q1)]
...

final(qk) = '*', si qk es estado final.
final(qk) = ' ', si qk no es estado final
ejemplo

AFD a Expresión regular

AFND a AFD

Transiciones:
Línea 1: q1 sigma1 p1
Línea 2: q2 sigma1 p2
...
Línea N: qN sigmaN pN

Conjunto de estados iniciales
Conjunto de estados finales
ejemplo

AFND a AFD

e-mail: