Autómatas finitos deterministas (AFD)
• Determinista: para cada entrada, existe un único estado al que el autómata puede llegar partiendo del estado actual • Consta de:

Tabla de transiciones
Representación tabular de la función " • filas: estados • columnas: entradas • estado inicial: flecha • estados finales: *
0 ->q0 q2 q1 q2 1 q0 q1 q1

Tema 2: Autómatas finitos

– un conjunto finito de estados, Q – un conjunto finito de símbolos de entrada, ! – una función de transición (") que, dados un estado y una entrada, devuelve un estado. "(q, a) = p – un estado inicial (uno de los estados de Q), q0 – un conjunto de estados finales o de aceptación (subconjunto de Q), F

• A = (Q, !, ", q0, F)

*q1 q2 Teoría de autómatas y …ver más…

Acosta)

Tema 2: Autómatas finitos

6

© Manuel Mucientes (Revisión: Juan C. Acosta)

Tema 2: Autómatas finitos

Autómatas finitos no deterministas
• • • • • AFN: capacidad de estar en varios estados simultáneamente Aceptan los lenguajes regulares, igual que los AFD Más compactos y fáciles de diseñar que los AFD Siempre es posible convertir un AFN a un AFD Ejemplo: AFN que acepta las cadenas terminadas en 01

Ej: acepta la 00101?

© Manuel Mucientes (Revisión: Juan C. Acosta)

Tema 2: Autómatas finitos

10

Definición de los AFN
• A = (Q, !, ", q0, F) • " devuelve ahora un conjunto de estados, y no un solo estado

Construcción de subconjuntos
• Dado el AFN N= (QN, !, "N, q0, FN), obtener el AFD D= (QD, !, "D, {q0 }, FD) tal que L(D)=L(N)
– Alfabetos iguales – Estado inicial de D: conjunto con el estado inicial de N – QD: conjunto de subconjuntos de QN. Si QN tiene n estados, QD tendría 2n. (pueden simplificarse estados no accesibles a partir del inicial) – FD: conjunto de subconjuntos S de QN tales que S ' FN & % – Para cada S ( QN y cada símbolo de entrada a del alfabeto:

• Ejemplo: AFN que acepta las cadenas terminadas en 01
– A=({q0, q1, q2}, {0, 1}, ", q0, {q2}) 0 ->q0 {q0, q1} q1 q2 % % 1 {q0} {q2} %
Tema 2: Autómatas finitos 11

"D ( S , a ) #

p en S

!"

N

( p, a )

© Manuel Mucientes (Revisión: Juan C. Acosta)

© Manuel Mucientes (Revisión: Juan C. Acosta)

Tema 2: