¿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? n
automata
finite-automata
saadtaame
fuente
fuente
Respuestas:
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 ϵ AL A n L n+1 n a ϵ 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 1 ∖ S 2 w = w ( A - a ) w ( S 1 ) w ∉ L w ( S 2 ) w ∈ LL 2n S1,S2 A w(S1),w(S2) S1,S2 a∈S1∖S2 w=w(A−a) w(S1)w∉L w(S2)w∈L
fuente
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 nn≥1 (0+1)∗1(0+1)n−1 n+1 2n
fuente
Supongo que quiere decir que el DFA óptimo tiene estados. Tal vez esto no te dé estados, pero es .2 n Ω ( 2 n )2n 2n Ω(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 }c Lc={ww∣w∈{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 )Lc O(c) Ω(2c)
fuente
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,…,n−1} An=(Qn,A,En,{0},{0})
fuente