Comment prouver que les DFA des NFA peuvent avoir un nombre exponentiel d'états?

20

Tous les automates finis non déterministes peuvent être transformés en automates finis déterministes équivalents. Cependant, un automate fini déterministe ne permet qu'une seule flèche par symbole pointant à partir d'un état. Par conséquent, ses États devraient être membres de l'ensemble des États de la NFA. Cela semble indiquer que le nombre d'États de la DFA pourrait évoluer de façon exponentielle en termes de nombre d'États de la NFA. Cependant, je me demandais comment le prouver.

John Hoffman
la source
7
C'est une question raisonnable, et la construction n'est pas complètement évidente, mais cela pourrait quand même être une question de devoirs. Il serait donc utile d'entendre pourquoi vous voulez savoir.
il y a quelques constructions ici mais il semble que cela devrait être quelque part dans un document. Je ne connais pas de réf. pense aussi qu'il y a une construction telle que le NFA compte en binaire dans ses états actifs, et n'accepte qu'après environ transitions ...? 2n
vzn
Voir aussi cs.stackexchange.com/questions/3381/…
Gilles 'SO- arrête d'être méchant'

Réponses:

15

Une opération qui transforme un NFA en un autre NFA mais ne le fait pas pour un DFA est l'inversion (pointez toutes les flèches dans l'autre sens et échangez les états initiaux avec les états accepteurs). Le langage reconnu par l'automate transformé est le langage inversé .LR={un1u0u0un1L}

Ainsi, une idée est de chercher un langage qui a une construction asymétrique. À l'avenir, ce langage devrait être reconnu en inspectant les premiers symboles, ne nécessitant que n + O ( 1 ) états. En reculant, il devrait être nécessaire de conserver une mémoire des n derniers états, ce qui nécessite A n + O ( 1 ) états où A est la taille de l'alphabet.nn+O(1)nAn+O(1)A

Nous recherchons un langage de la forme M n est constitué de mots de longueur n , S est un sous-ensemble non trivial de l'alphabet, et M ne fournit aucune autre contrainte. Nous pourrions aussi bien choisir l'alphabet le plus simple A = { a , b } (un alphabet singleton ne fera pas l'affaire, vous n'y obtenez pas de NFA plus petits) et M = A . Un S non trivial signifie S = { a } . Pour ce qui est deMnSMMnnSMA={a,b}M=ASS={a} , nous exigeons qu'il ne soit pas corrélé avec S (de sorte que le DFA pour le langage inversé devra garder la mémoire de S ): prendre M n = A n .MnSSMn=An

Soit donc . Il est reconnu par un DFA simple avec n + 2 états.Ln=(a|b)na(a|b)n+2

dfa

L'inverser donne un NFA qui reconnaît .LnR=(a|b)a(a|b)n

nfa

Le DFA minimal qui reconnaît a au moins 2 n + 1 états. En effet, tous les mots de longueur 2 n + 1 doivent atteindre des états distincts dans le DFA. (En d'autres termes, ils appartiennent à des classes d'équivalence Myhill-Nerode distinctes .) Pour le prouver, prenez deux mots distincts u , v A n + 1 et soit k une position où ils diffèrent ( u kv k ). Sans perte de généralité, supposons u kLnR2n+12n+1u,vAn+1kukvk et v k = b . Alors u b kL R n et v b kL R n ( b k est une extension distinctive pour u et v ). Si u et v conduisaient au même état dans un DFA reconnaissant L R n, alors u b k et v b kuk=avk=bubkLnRvbkLnRbkuvuvLnRubkvbk, ce qui est impossible car l'un mène à un état acceptant et l'autre non.

Remerciements: cet exemple a été cité sur Wikipedia sans explication. L'article fait référence à un article que je n'ai pas lu qui donne une limite plus
stricte : Leiss, Ernst (1981), "Représentation succincte des langages réguliers par les automates booléens", Theoretical Computer Science 13 (3): 323-330, doi: 10.1016 / S0304-3975 (81) 80005-9 .

Gilles 'SO- arrête d'être méchant'
la source
nQQ2nn2n
1
n2nnn 2n2n1
hmm ... après avoir lu votre réponse deux fois et à partir du commentaire "Mais ici, nous voulons voir que la limite est atteinte" maintenant j'aurais pu comprendre. Merci.
Grijesh Chauhan
8

Ln={x1,x2,,xk#xk+1:i{1,,k} with xi=xk+1}

Ln{#,1,,n}

O(n)Lnnii3

Ln2O(n){1,,n}

Je suis presque sûr que le livre de Sipser a cet exemple.

Gars
la source
La construction dans le livre de Siper produit un DFA avec exactement 2 ^ n états. Si le NFA a le jeu d'états Q, alors le jeu d'états du DFA est Pow (Q) afin de simuler tous les états `` parallèles '' possibles dans lesquels une migration NFA se trouve. (Modifier pour ajouter une opinion sur la portée de la question) Étant donné que le la construction utilisée pour cela dans un texte standard montre clairement la possibilité d'un nombre exponentiel d'états, il me semble que ce n'est pas un niveau de recherche. Peut convenir cependant comme demande de référence.
Logan Mayfield
8

nn2n

Cet exemple montre également que les NFA peuvent subir une explosion exponentielle sous complémentation. En effet, il est connu que toute NFA (ou même grammaire hors contexte) pour la langue de tous les mots contenant tous les symboles de l'alphabet doit avoir un nombre exponentiel d'états.

Yuval Filmus
la source
1
σΣ(Σσ)
ΣnO(n2)2n2n
Le point de cet exemple est que l'explosion correspond exactement à la construction de l'ensemble d'alimentation. Il existe un exemple binaire avec la même explosion, mais c'est plus compliqué.
Yuval Filmus
Oui, c'est un bel exemple.
6005
1
O(nlogn)