Automatas finitos no deterministas

Autómatas Finitos No Deterministas
Llamaremos "autómata finito no determinista" (AFND) a la séxtupla:
A = ( å , Q, f, q0, F, T ), donde:
* å , Q,q0, F significan lo mismo que en un autómata finito determinista.
* f es una aplicación de Q x å en el conjunto de las partes de Q
* T es una relación definida sobre pares de elementos de Q, donde p, q Î Q están en relación T( serepresentará por pTq, o (p,q)Î T) si existe una transición del estado p al estado q por medio de la palabra vacía l (l -transición).
Ejemplo: Sea el autómata finito no determinista:
({ a, b} , { p, q, r, s} , f, p, { p, s} , { (q,s), (r,r), (r,s), (s,r)} ), donde f se define asi:
f(p,a)={ q} f(p,b)=Æ
f(q,a)={ p,r,s} f(q,b)={ p,r}
f(r,a)=Æ f(r,b)={ p,s}
f(s,a)=Æ f(s,b)=Æ
 
Representación
EnDiagrama: Con tantos nodos como estados.
Pueden sobrar o faltar arcos de un estado a otro
Si f(p,a)=Q1, trazaremos una rama dirigida desde p hasta cada uno de los estados del conjunto de estados Q1, con la etiqueta a.
Pueden existir arcos de un estado a otro por medio de l , en el caso de pTq, que trazaremos una rama desde p hasta q con la etiqueta l .
 
 
Ejemplo (continuación):

 
Tabla: Tendrátantas filas como estados, y tantas columnas como elementos de å ,
más una columna adicional encabezada por la palabra vacía l , esta será la clumna reservada a las l -transiciones.
Ejemplo (continuación) :
  | a | b | l |
® p | { q} |   |   |
q | { p,r,s} | { p,r} | { s} |
r |   | { p,s} | { r,s} |
*s |   |   | { r} |
 
Relación T
Sabemos que: (p,q) Î T*, donde T* = T0 È T1 È T2 È....
Utilizaremos las matrices booleanas de representación T, para representar si un estado q es accesible desde un estado p mediante una l -transición.
Primero se representará la matriz booleana de representación de T, o, lo que es lo mismo, la matriz booleana que representa la posibilidad de transitar a otro estado a partir de una l -transición:
 
 T | p | q | r | s |
p | 0 | 0 | 0 | 0 |q | 0 | 0 | 0 | 1 |
r | 0 | 0 | 1 | 1 |
s | 0 | 0 | 1 | 0 |

 T* | p | q | r | s |
p | 0 | 0 | 0 | 0 |
q | 0 | 0 | 1 | 1 |
r | 0 | 0 | 1 | 1 |
s | 0 | 0 | 1 | 1 |
 
Ahora se hace la clausura transitiva de la relación T, es decir, la relación T*, que no es más que calcular la accesibilidad de unos estados a otros mediante un número de l -transiciones mayor.
Lo que se ha hechoen esta clausura no es más que calcular aquellos estados q, que a partir de un estado p, es posible acceder mediante l -transiciones. Esto se puede ver tanto en el diagrama de estados, como en la matriz booleana de la relación T. Se puede observar que el estado r no accesible desde q mediante una l -transición, sin embargo si será accesible mediante dos l -transiciones. Este también será el casodel estado s y su acceso a sí mismo mediante l -transiciones.
 
Extensión de f a palabras
Ahora vamos a definir f’ como una nueva función de transición que, en lugar de actuar sobre letras del alfabeto de entrada, actúe sobre palabras (que incluyan la palabra vacía l ). Es decir: f’: Q x å * ® P(Q) (P(Q), partes de Q)
a) f’(q,l ) = { p | q T* p} , para todo qÎ Q
b) Sea x = a1a2...an , n > 0. Entonces, f’(q,x) = { p | p es accesible desde q mediante la cadena de entrada l i0a1l i1a2... anlin} para todo qÎ Q (la sucesión anterior es idéntica a x).
Ejemplo (en el autómata anterior):
f’(p,l ) = { p} f’(q,l ) = { q,r,s}
f’(r,l ) = { r,s} f’(s,l ) = { r,s}
f’(p,a) = { q,r,s} f’(p,b) = Æ
f’(q,a) = { p,r,s} f’(q,b) = { p,r,s}
f’(r,a) = Æ f’(r,b)={ p,r,s}
f’(s,a) = Æ f’(s,b) = {p,r,s}
f’(p,aa) = { p,r,s} f’(p,ab) = { p,r,s}
f’(q,aa) = { q,r,s} f’(r,ba) = { q,r,s}
 
Lenguaje aceptado por un AFND
El L(AFND) estará formado por el conjunto de cadenas que acceden a un estado final: L(AFND) = { x | x Î å * | f (q0, x) = Ci | $ qf Î Ci | qf Î F }
La cadena vacía l , es aceptada por el AFND , cuando el estado final es un estado final: l Î L(AFND) si q0 Î F Ú q0 T* qf | qf Î F...