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

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.

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é .$L^R = \{u_{n-1}\ldots u_0 \mid u_0\ldots u_{n-1} \in L\}$

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.$n$$n + O(1)$$n$$A^n + O(1)$$A$

Nous recherchons un langage de la forme où 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 de$M_n S M'$$M_n$$n$$S$$M'$$\mathscr{A} = \{a,b\}$$M' = \mathscr{A}^*$$S$$S = \{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 .$M_n$$S$$S$$M_n = \mathscr{A}^n$

Soit donc . Il est reconnu par un DFA simple avec n + 2 états.$L_n = (a|b)^n a (a|b)^*$$n+2$

L'inverser donne un NFA qui reconnaît .$L_n^R = (a|b)^* a(a|b)^n$

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 k ≠ v k ). Sans perte de généralité, supposons u $L_n^R$$2^{n+1}$$2^{n+1}$$u,v \in \mathscr{A}^{n+1}$$k$$u_k \ne v_k$ et v k = b . Alors u b k ∈ L R n et v b k ∉ L 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 $u_k = a$$v_k = b$$u b^k \in L_n^R$$v b^k \notin L_n^R$$b^k$$u$$v$$u$$v$$L_n^R$$u b^k$$v b^k$, 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 .

$L_n = \{ x_1, x_2, \ldots, x_k \# x_{k+1}: \exists i \in \{1, \ldots, k\} \text{ with } x_i = x_{k+1} \}$

$L_n$$\{\#, 1,\ldots, n \}$

$O(n)$$L_n$$n$$i$$i$$3$

$L_n$$2^{O(n)}$$\{1,\ldots, n\}$

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

$n$$n$$2^n$

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.