NFA con número exponencial de estados cuando se determinan

10

¿Cómo puedo construir un ejemplo de un DFA que tiene estados donde el NFA equivalente tiene estados? Obviamente, el conjunto de estados del DFA debe contener todos los subconjuntos del conjunto de estados del NFA, pero no sé cómo comenzar. ¿Alguna sugerencia para ponerme en el camino correcto? n2nn

saadtaame
fuente
Esta pregunta es algo poco clara. En general, hay un número infinito de DFA equivalentes para cualquier lenguaje regular dado, y un número infinito de NFA equivalentes para un lenguaje regular dado. Si desea DFA mínimos con 2n estados, esto no siempre es posible, ya que diferentes NFA pueden reconocer el mismo idioma y tener diferentes números de estados, pero corresponden al mismo DFA mínimo. Si, además, solo desea considerar los NFA "mínimos", esto se vuelve algo más interesante ...
Patrick87
2
Patrick, creo que el OP significa un ejemplo en el que el DFA mínimo es exponencialmente mayor que el NFA mínimo.
Yuval Filmus
@ Patrick87 No estoy buscando un algoritmo. Todo lo que quiero es un ejemplo de un par de máquinas: DFA con 2n estados y NFA con n estados que aceptan el mismo idioma.
saadtaame
@saadtaame: Eso es trivial: tome cualquier DFA y agregue suficientes estados para llegar a 2n . Un ejemplo interesante son aquellos en los que el DFA mínimo equivalente tiene tantos estados.
Raphael
1
Tenga en cuenta que el artículo de Wikipedia sobre minimización de DFA hace referencia a ejemplos adecuados (aunque usted mismo debe descubrir el pequeño NFA).
Raphael

Respuestas:

18

El ejemplo estándar es el lenguaje de todas las palabras sobre un alfabeto de tamaño que no contiene todas las letras diferentes. Hay una aceptación NFA con estados (o estados si permite que múltiples estados de partida): primera adivinar una carta la que se encuentra, entonces ir (con un -Mover) a un estado de aceptación con la libre bucles de todas las cartas que no sean .A n L n + 1 n a ϵ ALAnLn+1naϵA

Cualquier DFA para requiere al menos estados. Esto se puede ver usando el teorema de Myhill-Nerode. Supongamos que sean dos subconjuntos diferentes de y palabras que contienen todas y solo las letras en , respectivamente. Sin pérdida de generalidad, suponga , y deje . Entonces mientras que .2 n S 1 , S 2 A w ( S 1 ) , w ( S 2 ) S 1 , S 2 a S 1S 2 w = w ( A - a ) w ( S 1 ) w L w ( S 2 ) w LL2nS1,S2Aw(S1),w(S2)S1,S2aS1S2w=w(Aa)w(S1)wLw(S2)wL

Yuval Filmus
fuente
10

Este es un ejercicio en el libro "Autómatas finitos" de Mark V. Lawson Heriot-Watt University, Edimburgo, página 68:

Deje . Muestre que el lenguaje puede ser reconocido por un autómata no determinista con estados. Muestre que cualquier autómata determinista que reconozca este lenguaje debe tener al menos estados. Este ejemplo muestra que un aumento exponencial en el número de estados al pasar de un autómata no determinista a un autómata determinista correspondiente a veces es inevitable.( 0 + 1 ) 1 ( 0 + 1 ) n - 1 n + 1 2 nn1(0+1)1(0+1)n1n+12n

MK Dadsetani
fuente
10

Supongo que quiere decir que el DFA óptimo tiene estados. Tal vez esto no te dé estados, pero es .2 n Ω ( 2 n )2n2nΩ(2n)

De "Complejidad de comunicación" de Kushilevitz y Nisan en el ejercicio 12.6:

"Para algunos [enteros no negativos] constantes , considere el lenguaje (finito) ".L c = { w w w { 0 , 1 } c }cLc={www{0,1}c}

y el libro continúa pidiéndole que pruebe que puede encontrar un co-NFA que reconoce que usa estados y también que no puede hacerlo mejor que los estados para un DFA. O ( c ) Ω ( 2 c )LcO(c)Ω(2c)

Timothy Sun
fuente
Además, la prueba de la segunda parte "requiere" complejidad de comunicación, por lo que esto podría no ser adecuado para sus propósitos.
Timothy Sun el
¡Gracias por la respuesta! ¿Qué quieres decir con co-NFA?
saadtaame
Básicamente, cambie "aceptar" por "rechazar" en la definición de un NFA. Es decir, si ninguno de los caminos posibles conduce a un estado de rechazo, usted acepta, de lo contrario, rechaza.
Timothy Sun el
De hecho, el límite inferior de sigue fácilmente de Myhill-Nerode. (De hecho, puede obtener algo como ( c + 1 ) 2 c .) Pero mi co-NFA usa estados Θ ( c 2 ) . 2c(c+1)2cΘ(c2)
Yuval Filmus
Los idiomas finitos son algo aburridos a este respecto. Ver también aquí .
Raphael
9

Esta es una respuesta tardía, pero aparentemente nadie dio la solución óptima. Tome , Q n = { 0 , 1 , , n - 1 } et A n = ( Q n , A , E n , { 0 } , { 0 } ) , con E n = { ( i , a , iA={a,b}Qn={0,1,,n1}An=(Qn,A,En,{0},{0})

En={(i,a,i+1)0in1}{(n1,a,0)}{(i,b,i)1in1}{(i,b,0)1in1}}
Este NFA en un alfabeto de dos letras tiene estados, solo un estado inicial y uno final y su DFA mínimo equivalente tiene 2 n estados.n2n
J.-E. Alfiler
fuente
3
¡Muy inteligente! El lenguaje aceptado por este autómata es , donde W n - 1 consta de todas las palabras que contienen la letra a como máximo n - 1 veces. (an+aWn1b)Wn1an1
Yuval Filmus
2
@ yuval-filmus Este ejemplo no es mío. Quería dar una referencia, pero por el momento no recuerdo dónde lo vi.
J.-E.