Post on 27-Jun-2020
transcript
Autómatas finitos no
deterministicos
AFND
Una extensión a los autómatas finitos deterministas
que permite que cada nodo del diagrama de
estados salga un número mayor o menor de flechas
con símbolos del alfabeto.
Se permite que falte la flecha de alguno de los
símbolos del alfabeto, o que haya varias flechas
que salgan de un sólo nodo con la misma etiqueta.
Podemos considerar que los AFD son casos
especiales de AFND.
Ejemplo
w=“01101”
Definición
Un AFND M es una estructura M=<Q, ∑, δ, q0, F>
donde Q, ∑, q0 y F tienen el mismo significado que
para los AFD, pero la función de transición está
definida por
δ: Q Χ ∑ → 2Q
Donde 2Q es el conjunto potencia de Q.
δ regresa conjuntos de estados en vez de un sólo
estado siguiente: la intensión es que δ(q,a) denote
el conjunto de todos los estados p tales que existe
una transición de q hacia p etiquetada con a.
Extensión inductiva de δ
Extendemos inductivamente a δ para reconocer
cadenas
1. Caso base:
No hay cambio de estado si no se lee algún
símbolo.
2. Paso inductivo
Esta condición indica que partiendo del estado q y
leyendo la cadena de entrada w seguida del
símbolo a el AFND puede estar en el estado p si y
sólo si se puede alcanzar algún estado r del cual
mediante una transición etiquetada con a alcanza el
estado p.
Operacionalmente, primero debemos obtener el
conjunto de estados que son alcanzables leyendo w
(recursivamente) y entonces para ese conjunto de
estados, evaluar δ(r,a).
3. Extendemos la función para recibir como argumentos conjuntos de estados:
Donde
Nótese que en general también podemos plantear lo anterior de la siguiente forma:
Donde R=
Lenguaje de un AFND
L(M) denota al lenguaje aceptado por un
AFND M:
Por la definición anterior, cualquier AFD M=
<Q, ∑, δ, q0, F> es equivalente a un AFND
N=<Q, ∑, δ’, {q0}, F> donde δ’(p,q)={δ(p,a)}.
Ejemplo
M3 = <Q, ∑, δ, q0, F>, donde
Q={q0,q1,q2,q3,q4}, F={q2}, ∑={‘0’,’1’}
Ejemplo Sea la cadena de entrada w=“01100”. La secuencia
de transiciones que realiza M3 para examinar w son:
Nótese que se va evaluando recursivamente sobre
la longitud de la cadena de entrada hasta que ésta
sea mínima sólo entonces se detiene la recursión y
se consulta la tabla de δ.
Ejemplo
Por lo tanto si entonces M3
acepta la cadena w.
Ejercicio
Demuestre que la cadena v=“0101” no
pertenece al lenguaje del AFND M3.
Ejercicio
Para el AFND M1 construye dos cadenas (de
longitud al menos 5) y muestra si aceptan o
rechazan cada cadena utilizando la
evaluación formal con δ y la evaluación
mostrando el árbol correspondiente. Dibuja el
grafo.
Ejercicio
Usando el diagrama, muestra los elementos
del AFND y presenta dos cadenas que
acepte el autómata.
Equivalencia entre AFD y AFND
El AFND al examinar una cadena de entrada
construye un árbol de estados y el AFD
correspondiente encapsula los estados en
paquetes, donde cada paquete corresponde
al conjunto de estados de cada nivel del
árbol.
Ejemplo
Sea M4=<{q0,q1,q2}, {0,1},δ,q0,{q1}>
Obtener su AFD
Ejemplo
Construir los paquetes:
δ(q0, 0)={q0,q1}
δ(q0, 1)={q0,q1,q2}
δ({q0,q1}, 0)={q0,q1} υ Ø= {q0,q1}
δ({q0,q1}, 1)={q0,q1,q2} υ Ø= {q0,q1,q2}
δ({q0,q1,q2}, 0)={q0,q1} υ Ø υ {q1}= {q0,q1}
δ({q0,q1,q2}, 1)={q0,q1,q2} υ Ø υ {q2}= {q0,q1,q2}
δ’ 0 1
-> [q0] [q0,q1] [q0,q1,q2]
F:[q0,q1] [q0,q1] [q0,q1,q2]
F:[q0,q1,q2] [q0,q1] [q0,q1,q2]
Nótese que el primer de δ’ se obtuvo al convertir en
paquetes el primer renglón de δ.
El conjunto de estados finales F’ consiste de todos
los paquetes que contengan al menos un estado
final de F: en el ejemplo F’={[q0,q1], [q0,q1,q2]}
La traza de estados para la cadena “001” para el
AFD M4’ es:
Mientras que M4 hace lo siguiente:
Ejemplo
Teorema
Sea L un conjunto (lenguaje) aceptado por un
AFND, existe un AFD que acepta L.
Dem. Sea M=<Q, ∑, δ, q0, F> un AFND que acepta
L. Se define un AFD M’=<Q’, ∑, δ’, q0’, F’ > de la
siguiente forma
Q’= 2Q es el conjunto potencia de Q.
F’ contiene subconjuntos que a su vez contengan al menos
un estado en F.
En la construcción para transformar un AFND a AFD, un
elemento de Q’ sera denotado por un paquete [q1,…,qn],
donde cada qi en Q.
Se define δ’ de la siguiente manera:
δ’([q1,q2,…,qi],a) = [p1,p2,…,pi]
Siempre que δ({q1,q2,..,qi},a)={p1,p2,…,pi}
δ’(q0’,x) = [q1,q2,q3,…,qj]
Siempre que δ(q0,x) = { q1,q2,q3,…,qj }
Aplicamos inducción sobre la longitud de
cadena x
Caso base |x|=0, x=ɛ δ’(q0, ɛ)=[q0] pues δ(q0, ɛ)={q0}
Paso inductivo Suponemos que la HI se cumple para w donde |w| ≤ m. Sea wa
una cadena tal que |wa| = m+1 (a en ∑). Entonces se debe cumplir que
δ’(q0’, wa)= δ’(δ’(q0’, w),a)
Por la HI sabemos que δ’(q0’, w)= [p1,p2,…,pj ]
Si y sólo si δ(q0, w)={p1,p2,…,pj}
Y por la definición de δ’:
δ’([p1,p2,…,pj], a)= [r1,r2,…,rk]
Si y sólo si δ({p1,p2,…,pj}, a)= {r1,r2,…,rk}
Por lo tanto
δ’(q0’, wa)= δ’(δ’(q0’, w),a) = δ’([p1,p2,…,pj], a)= [r1,r2,…,rk]
Si y sólo si
δ(q0, wa)={r1,r2,…,rk}
Finalmente,
Por lo tanto L(M) =L(M’).
Ejercicio
Obtener el AFD de:
Solución
El AFD es
Proceso iterativo
Obtener todos los paquetes que se pueden
llegar desde [q0], esto evita que se calculen
estados que no son accesibles y por tanto,
inútiles.
Para cada paquete nuevo, obtener todos los
paquetes que se puede llegar leyendo cada
símbolo del alfabeto.
Repetir el paso anterior hasta que ya no se
encuentre algún paquete nuevo.
Ejercicios
Obtener el AFD de