Ejemplo de AFN
Ej. Diseña un AFN que acepte todas las cadenas que contengan dos ceros
consecutivos o dos unos consecutivos.
Solución
AFN
q0
q1
q2
1
0
Ejemplo:
q3
q0
0
q0
1
0
q0
1
0
q4
1
q3
0
q0
0
q1
0
q0
0
q3
1
q0
1
q3
q1
0
q4
1
q4
Equivalencia de los AFD’s y los AFN’s
•
•
•
AFD ⊆ AFN
Dado que todo AFD es un AFN, es claro que la clase de lenguajes aceptado
por los AFN´s incluye los aceptados por los AFD.
AFN ⊆ AFN
Teorema. Sea L un lenguaje aceptado por un AFN. Entonces existe un
AFD que acepta L.
Demostración
Sea M= (K, Σ, δ, q0, F) un AFN que acepta el lenguaje L.
Definamos un DFA. M´= (K’, Σ’, δ’, q0’, F’) de tal manera que:
1) Los estados de M´son todos subconjuntos del
conjunto de estados de M. Esto es:
K´ = 2k = P(K)
Los nombres de dichos conjuntos se generarán de la siguiente manera:
[q1,…, qi] es un solo estado del AFD correspondiendo a un conjunto
de estados en 1 AFN.
Equivalencia de los AFD’s y los AFN’s
2) F´es el conjunto de todos los estados en K´ que contenga estado que
pertenezca a F.
3) q’0 = [q0]
4)Definimos δ’ como:
δ’([q1, q2,…., qi] , a) = [P1, P2,…, Pi]
Si y sólo si
δ({q1, q2,…., qi} , a) = {P1, P2,…, Pi}
Equivalencia de los AFD’s y los AFN’s
Demostremos ahora por inducción sobre la longuitud de la cadena de entrada,
que:
δ’(q´0 , x) = [q1, q2,…., qi]
Si y solo si
δ(q0 , x) = {q1, q2,…., qi}
Demostración:
1) Para |x| = 0 , x = ε
δ’(q´0 , ε) = [q0]
δ(q0 , ε) = {q0}
2) H.I. , |x| = m
δ’(q´0 , x) = [r1, r2,…., rn]
 δ(q0 , x) = {r1, r2,…., rn}
3) Demostrar para |w| = |xa| = m+1
δ’(q´0 , xa) = δ’( δ’(q´0 , x) a)
Equivalencia de los AFD’s y los AFN’s
Por definición de δ’ tenemos:
δ’ ([r1, r2,…., ri] , a) = [P1, P2,…, Pi]
 δ ({r1, r2,…., ri} , a) = {P1, P2,…, Pi}
Así tenemos que:
δ’( δ’(q´0 , x) a) = δ ({r1, r2,…., ri} , a) = {P1, P2,…, Pi}
∴ AFN = AFD
LQQD
Problema. Sea M = ({q0, q1}, {0,1}, d, q0, {q,})
un AFN , donde:
d
q0
q1
0
1
{q0,q1} {q,}
f
{q0, q1}
1
q0
Construya un AFD que acepte L(M)
0
0
1
1
q1
Autómata Finito No-Deterministico con
Movimiento - ε
Ejemplo:
1
Start
0
q0
ε
q1
ε
q2v
2
Definición: Un autómata finito no- determinístico con movimientos – e
consiste en un quíntuplo (K, S, d, q0, F) en donde K , S, q0 y F se
definen de la misma manera que el autómata finito no –
determinístico, y con:
δ : K x ( Σ ∪ {ε}) → 2K
La intención es que d(q, a) consista de todos los estados Pj, tales que
existe una transición etiquetada a, desde q hasta Pj. En donde a es el
símbolo e o cualquier símbolo en S.
Autómata Finito No-Deterministico con
Movimiento - ε
Función de transición del ejemplo anterior:
0 1
2
e
q0 {q0} f
f {q1}
q1 f {q1} f {q2}
q2 f
f {q2} f
Def. denominamos CERRADURA – e(q) a todos aquellos vértices (estados) rj,
tales que existe una ruta de p a q, consistente en transiciones e.
ej. CERRADURA
ej. CERRADURA – e(q0) = {q0, q1, q2}
Autómata Finito No-Deterministico con
Movimiento - ε
Def. llamamos CERRADURA - ε (q) al conjunto de todos los nodos p tales que
existe una ruta de q a p etiquetada ε.
Es fácil extender esta definición a la CERRADURA - ε(p) en donde P es un
conjunto de estados:
Sea Uqεp CERRADURA – ε (q), definimos δ’ como:
1) δ’ (q, ε ) = CERRADURA - ε (q)
2) Para w ε Σ* y a ε S ,
δ’(q, wa) = CERRADURA – ε (P)
en donde P = {p | para algún r ε δ’(q,w) y p ε d(r,a)}
Autómata Finito No-Deterministico con
Movimiento - ε
Es conveniente extender d y d’ a conjuntos de estados de la manera siguiente:
1)
δ (R, a ) = UqεR δ (q, a )
2)
δ’ (R, w ) = UqεR δ’ (q, w )
Para conjuntos en estados R.
Definamos L(M) el lenguaje aceptado por un M= (Q, S, d, q0, F) (un AFN con
MOVs - ), ser:
L(M) = {w| δ’ (q0 , w) ∩ F ≠ f }
Equivalencias de entre un AFN y un
AFN con movimientos - ε
Teorema. Si L es aceptado por un AFN con MOVs – ε
Demo. Sea M = (Q, S, d, q0, F) un AFN con MOVs - ε .Construya un M´= (Q, S,
d, q0, F´) donde:
F´= F ∪ {q0} si la CERRADURA - ε (q0) contiene
algún estado de F.
F
caso extraño
y δ’ (q0, x) = Ŝ (q, a) para q ε Q y a ε Σ
Resta demostrar por inducción sobre |x| que
δ’(q0, x) = Ŝ (q0, x)
Base : |x| = 1  x= a , a ε Σ.
 δ’(q0, a) = Ŝ (q0, a) por def. de δ´
Equivalencias de entre un AFN y un
AFN con movimientos-ε
Inducción: |x| > 1 , Sea x = wa , a ε Σ entonces:
δ’(q0, wa) = δ’(δ’(q0, w) a)
Por Hipótesis de Inducción
δ’(q0, w) = Ŝ(q0, w)
Sea Ŝ (q0, w) = r , por demostrar d´(r , a) = Ŝ (q0, wa).
d´(r, a) = UqεR d´(q, a) =  UqεR Ŝ (q, a)
Entonces por la regla 2 de la definición de Ŝ
δ’(q0, wa) = Ŝ (q0, wa)
Ejemplos
1.
q0
q1
q2
q3
Descargar

Autómatas de Estados Finitos no determinísticos