grafos

ay muchas formas de implementar una AFND:
Convertir al equivalente AFD: en algunos casos esto puede causar una explosión exponencial en el tamaño del autómata, y así un espacio auxiliar proporcionalal número de estados en el AFND (como el almacenamiento del valor del estado requiere en la mayoría de un bit por cada estado en el AFND).
Mantener un conjunto de datos de todos los estados en quela máquina podría estar en la actualidad. Al consumir el último carácter de entrada, si uno de estos estados es un estado final, la máquina acepta la cadena. En el peor de los casos, esto puederequerir espacio adicional proporcional al número de estados en el AFND; si la estructura del conjunto usa un bit por estado del AFND, entonces esta solución es exactamente equivalente a la anterior.
Crearmúltiples copias. Por cada n forma de la decisión, el AFND crea hasta n-1 copias de la máquina. Cada uno de ellos entrara en un estado independiente. Si, al momento de consumir el último símbolo de laentrada, al menos una copia del AFND esta en un estado de aceptación, el AFND lo aceptará. (Esto también requiere un almacenamiento lineal con respecto al número de estados del AFND, ya que puedehaber una máquina por cada estado del AFND).
AFND-ε[editar · editar código]

Propiedades[editar · editar código]
Para todo p,q\in Q,, se escribe p\stackrel{\epsilon}{\rightarrow}q si y solo si a q sepude llegar desde p, yendo a lo largo de cero o más flechas \epsilon. En otras palabras, p\stackrel{\epsilon}{\rightarrow}q si y sólo si existe q_{1}, q_{2},\cdots q_{k}\in Q donde k\geq 0 tal queq_{1}\in T(p,\epsilon), q_{2}\in T(q_{1},\epsilon),\cdots q_{k}\in T(q_{k-1},\epsilon), q\in T(q_{k},\epsilon).
Para cualquier p\in Q, el conjunto de estados que se puede llegar a partir de p se llamaepsilon-closure o ε-closure de p y se escribe como
\,E(\{p\}) = \{ q\in Q : p\stackrel{\epsilon}{\rightarrow}q\}.
Para cualquier subconjunto P\subset Q, definir el ε-closure de P como
E(P) =...