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