Pregunta de NFA a DFA

Question

Primero, esta no es una pregunta que pide el algoritmo para convertir un NFA a DFA.

Se sabe (y se demuestra) que el DFA equivalente de un NFA tiene como máximo 2^norte Estados, a pesar de que la mayoría de las veces tendrá más o menos el mismo número de estados que el NFA.

¿Cómo puedo predecir una estimación para el número de estados que tendrá el DFA equivalente a NFA? ¿Qué tipo particular de NFA requerirá un DFA equivalente para tener 2^norte estados?

Mi razón para preguntar esto es poder "inventar" algunos NFA que ciertamente producirán, sin considerar la minimización, 2^norte - 1 Estados más el "Estado muerto".

Answer 1

El número de estados explota debido a no determinismo, que es la clave de tu pregunta.

Si toma un NFA, donde cada transición se determina de manera única, es decir, un NFA determinista, entonces no es más que un DFA normal. Sin embargo, una vez que tiene un estado en el que son posibles dos transiciones, difiere del DFA.

Considere el algoritmo de conversión y mire lo que sucede si tiene dos o más transiciones con la misma etiqueta para un estado. Aquí es donde necesita esos nuevos estados que corresponden a conjuntos de estados.

Entonces, la pregunta se reduce a descubrir cuántos de estos estados de superconjunto son realmente accesibles. Por supuesto, podría inventar un algoritmo elegante para eso, pero para obtener el número correcto, simplemente ejecute el algoritmo de conversión normal y elimine los estados inalcanzables.

En cuanto a un NFA con n estados para los cuales el DFA equivalente tiene 2^n estados piensan en explotar el no determinismo. La primera idea sería etiquetar todas las transiciones de la misma manera, sin embargo, eso no funciona demasiado bien. En su lugar, recuerde que debe poder llegar de alguna manera a todos los subconjuntos de estados con alguna etiqueta cada uno.

Si no cuenta el estado inicial, puede hacer la siguiente construcción: crear n nodos y para cada conjunto de 2^n cree una etiqueta única y en el NFA agregue una transición con esta etiqueta a cada nodo de ese conjunto. Esto le da un NFA con estados n +1 (1 es el estado inicial), donde el DFA requiere 2^n +1 estados. Por supuesto, se vuelve más complicado, una vez que quieres tener 2^n estados DFA después de la minimización.

Answer 2

Ok, comience con suponer que n -> n. Ahora, para cada transición no determinista donde de un estado puede terminar en X en otros estados, multiplique su estimación por x. Esto puede no ser preciso, ya que podría tener doble cuenta. Pero debería darte un límite superior.

Sin embargo, la única forma segura de construir un DFA correspondiente y luego contar los estados (creo).

Finalmente, probablemente pueda simplificar algunos de los DFA (y los NFA), pero esta es una historia completamente nueva ...

Answer 3

Tomemos en función de N, con el estado de inicio y el estado final N, este NFA A(N):

S a-> S
S b-> S
S a-> 0 // NOTE: only "a" allows you to leave state S
0 a-> 1
0 b-> 1
1 a-> 2
1 b-> 2
...
N-1 a-> N
N-2 b-> N
N

Debería ser obvio que esto acepta todas las cuerdas en [ab]* cuya nth de la carta es a.

La determinización de A(N) tiene que recordar las letras N-1 anteriores, de manera efectiva (necesita conocer todas las posiciones en esa ventana que fueron a, de modo que cuando la cadena termina inesperadamente, puede decir si había un a N hace letras).

No estoy seguro de si esto llega exactamente a la cantidad de estados que quería, pero está al menos dentro de un factor de 2, todos los subconjuntos de {0,...,N} son posibles, pero también siempre estás en S. Esto debería ser 2^(N+1) estados, pero A(N) tenido N+2 estados.

Answer 4

Para ampliar aún más la excelente respuesta de Jonathan Graehl.

Agregar a cada estado 0, 1, ..., N de A(N) Un autogloop etiquetado c, es decir, agregas las siguientes transiciones:
0 c-> 0
1 c-> 1
...
N c-> N

Luego asumiendo c nunca dispara, el DFA contiene lo mismo 2^(N+1) Estados del DFA de Jonathan. Sin embargo, cuando c se observa desde un estado {S,j,k,...,z} <> {S} llegamos al estado {j,k,...,z}. De ahí todos los subconjuntos de {S,0,...,N} son posibles excepto el conjunto vacío y el DFA tiene 2^(N+2)-1 Estados mientras A(N) posee N+2 estados.