Autómatas Finitos
Determinismo × No Determinismo
● Determinismo (AFD)
Los AFs que vimos hasta ahora funcionan así: cuando la
máquina está en un dado estado y lee el próximo símbolo
de entrada, sabemos cual será el próximo estado, está
determinado, el próximo estado es único.
Para cada cadena w, existe una única secuencia de
estados.
Llamamos eso de computación determinística.
● No Determinismo (AFN)
En una máquina no determinística, varias elecciones
pueden existir para un siguiente estado en cualquier punto.
Autómatas Finitos No Determinísticos
Considere un AFN N1 que acepta las cadenas sobre el alfabeto
{a,b} que poseen aa o bb como subcadena.
a
a,b q0 q1
b a
b a,b
q2 q3
En un AFN un estado puede tener cero, Todo estado de un AFD siempre tiene
una o muchas flechas saliendo para exactamente una flecha de transición
cada símbolo del alfabeto. saliendo para cada símbolo en el alfabeto
Autómatas Finitos No Determinísticos
● Vamos a construir un AFN que acepta cadenas con un
número par de 1s o ímpar de 0s a partir de esos AFDs:
0 0
1
q1 q2
ε 1
1 1
q0
0
ε q3 q4
En general, un AFN puede 0
tener flechas rotuladas con
miembros del alfabeto o con ε.
Autómatas Finitos
La computación en un AFN
● No determinismo puede ser visto como una especie de
computación paralela en la cual múltiples e
independientes procesos pueden estar ejecutándose
concurrentemente.
● La máquina puede estar con varios estados activos al
mismo tiempo
Autómatas Finitos - La computación en un
AFN 0,1
1 0,ε 1
0,1 q1 q2 q3 q4
● Después de leer un símbolo, la máquina puede dividirse en
múltiples copias de sí misma y sigue todas las posibilidades en
paralelo.
● Si existieren elecciones subsecuentes, la máquina se divide
nuevamente.
● Si el próximo símbolo leido no aparece en cualquiera de las flechas
saliendo del estado ocupado por una copia de la máquina, aquella
copia muere, juntamente con la ramificación de la computación
asociada a ella.
● Finalmente, si cualquiera de esas copias de la máquina está en un
estado de aceptación en el final de la entrada, el AFN acepta la
cadena de entrada.
Autómatas Finitos
La computación en un AFN
0,1 q1
1 0,ε 1
0,1 q1 q2 q3 q4
q1
q1 q2 q3
Entrada 010110 X
q1 q3
Lectura: 0 1 0 1 1 0
q1 q2 q3 q4
X
q1 q2 q3 q4 q4
X
q1 q3 q4 q4
Autómatas Finitos No Determinísticos
Descripción Formal
● En un AFD la función de transición toma un estado y un
símbolo de entrada y produce el próximo estado.
● En un AFN la función de transición toma un estado y un
símbolo de entrada o la cadena vacía y produce el
conjunto de próximos estados posibles.
● De ese modo, vamos a usar la notación Σε = Σ ∪ ε.
● Y definir la función de transición de la siguiente forma:
δ: Q×Σε→℘(Q).
Autómatas Finitos No Determinísticos
Descripción Formal
Un autómata finito no determinístico es una 5-upla
(Q, Σ, δ, q0, F),
Donde:
1. Q es un conjunto finito denominado los estados,
2. Σ es un conjunto finito denominado alfabeto,
3. δ: Q×Σε→℘(Q) es la función de transición,
4. q0 ∈ Q es el estado inicial, y
5. F⊆Q conjunto de estados de aceptación (o finales).
Autómatas Finitos No Determinísticos
Descripción Formal: Ejemplo
0,1
1 0,ε q3
1
0,1 q1 q2 q4
La definición formal de ese AFN es (Q, Σ, δ, q1, F), donde:
Q={ } δ 0 1 ε
Σ={ } q1 { } { } { }
es el estado inicial q2 { } { } { }
F={ } q3 { } { } { }
q4 { } { } { }
Autómatas Finitos No Determinísticos
Descripción Formal: Ejemplo
0,1
1 0,ε q3
1
0,1 q1 q2 q4
La definición formal de ese AFN es (Q, Σ, δ, q1, F), donde:
Q = {q1,q2,q3,q4} δ 0 1 ε
Σ = {0,1} q1 {q1} {q1,q2} ∅
q1 es el estado inicial q2 {q3} ∅ {q3}
F = {q4} q3 ∅ {q4} ∅
q4 {q4} {q4} ∅
Otro ejemplo
• Vamos a computar la cadena 1001
Estados activos Lectura
1001
Más ejemplos
L(M) = { w ∈ {0,1}* : el 3er símbolo a partir del fin es 1}
• El no determinismo a veces es visto como un poder de
adivinación
Más ejemplos
{ w ∈ {0,1}* : 01 es subcadena de w}
Más ejemplos
Diseñe un AFN que reconozca
{ w ∈ {0,1}* : |w|1 ≥ 1 existe un n° par de 0s después el
último 1}
Más ejemplos
Diseñe un AFN que reconozca {w ∈ {a,b,c}* : el último
símbolo de w tiene al menos más de una ocurrencia}
Autómatas Finitos
¿Por qué dos modelos?
● Note que todo AFD es un AFN
● ¿Talvés los AFN sean más poderosos?
● Él ciertamente es más simple (más pequeño y fácil
de construir) en algunos casos que la versión
deterministica
Autómatas Finitos
Equivalencia entre AFNs y AFDs
● Autómatas finitos determinísticos y no determinísticos
reconocen la misma clase de lenguajes.
● Dos máquinas son equivalentes si ellas reconocen el
mismo lenguaje.
● Teorema: Todo autómata finito no determinístico tiene un
autómata finito determinista equivalente.
Autómatas Finitos
Equivalencia entre AFNs y AFDs
● Vamos a convertir un AFN en un AFD equivalente que lo
simule.
● Si k es el número de estados del AFN, el tiene 2k
subconjuntos de estados.
● Cada subconjunto corresponde a una de las
posibilidades que el AFD tiene que recordar, por tanto
AFD que simula el AFN tendrá 2k estados.
Equivalencia entre AFNs e AFDs
N (Q, Σ, δ,q0, F) a a
a,b 1 2 3
M (℘(Q), Σ, δ’, qo’, F’) δ a b
1 {1,2} {1}
Q’= ℘(Q)
2 {3} ∅
3 ∅ ∅
q0’= {1}
F’ = { R∈ Q’ | R contiene un
estado de aceptación de N}
δ’ (R,s)= unión de δ(q,s) para cada q ∈ R.
Equivalencia entre AFNs e AFDs
N (Q, Σ, δ,q0, F) a a
a,b 1 2 3
M (℘(Q), Σ, δ’, qo’, F’) ∅ δ a b
b 1 {1,2} {1}
Q’= ℘(Q)
2 {3} ∅
{1} {2} {3}
3 ∅ ∅
q0’= {1}
a b δ’ a b
{1,3} {2,3} {1} {1,2} {1}
{1,2}
{1,2} {1,2,3} {1}
a b
{1,2,3} {1,2,3} {1}
a {1,2,3} F’ = { R∈ Q’ | R contiene un
estado de aceptación de N}
δ’ (R,s)= unión de δ(q,s) para cada q ∈ R.
Equivalencia entre AFNs y AFDs
Introduciendo las transiciones ε
N = (Q, Σ, δ,q0, F)
1 δ a b ε
1 ∅ {2} {3}
b
ε
a 2 {2,3} {3} ∅
3 {1} ∅ ∅
a 2 3
a,b Para cualquier estado R de M definimos
E(R) como siendo la colección de estados
M = (℘(Q), Σ, δ’, qo’, F’) que pueden ser alcanzados a partir de R
yendo solamente a lo largo de flechas ε,
q0’= {1,3} incluyendo los propios miembros de R.
Formalmente, para R ∈ ℘(Q) sea
Luego q0’ = E({q0}) E(R) = {q | q puede ser alcanzado a partir
q0’ = E({1}) = {1,3} de R yendo a lo largo de 0 o más flechas ε}
N=(Q, Σ, δ,q0, F) 1
b a
ε
a 2 3
a,b
M=(℘(Q), Σ, δ’, qo’, F’)
δ’ (R,s)= unión de E(δ(q,s))
para cada q ∈ R.
N=(Q, Σ, δ,q0, F) 1
b a
ε
a 2 3
a,b
M=(℘(Q), Σ, δ’, qo’, F’)
δ’ (R,s)= unión de E(δ(q,s))
para cada q ∈ R.
a,b ∅
b
b a
{1} {2} {3}
a
b a b
a
{1,2} {1,3} {2,3} {1,2,3}
a b
Autómatas Finitos
Equivalencia entre AFNs y AFDs
Como acabamos de ver:
● Teorema: Todo autómata finito no determinista tiene
un autómata finito determinista equivalente.
Luego,
● Corolario: Un lenguaje es regular si y sólamente si
algún autómata finito no determinista la reconoce.
