D'un automate à une grammaire

Un non-terminal par état, le symbole initial étant celui de l'état initial :

$$\begin{array}{lcl}{Q}_0& \to & a{Q}_1\mid b{Q}_0\\ Q_1& \to & a{Q}_2\mid b{Q}_0\\ Q_2& \to & a{Q}_2\mid b{Q}_2\mid \epsilon \end{array}$$

La règle $Q_2\to \epsilon$ vient de ce que $2$ est acceptant, et elle seule.

Sur baab :

$$Q_0\Rightarrow b{Q}_0\Rightarrow ba{Q}_1\Rightarrow baa{Q}_2\Rightarrow baab{Q}_2\Rightarrow baab.$$

La dérivation reproduit lettre à lettre l'exécution $0\to 0\to 1\to 2\to 2$.

Ce qu'on remarque : toutes les règles ont la forme $A\to xB$ ou $A\to \epsilon$. Le non-terminal est toujours en dernière position, jamais au milieu, jamais deux à la fois. On appelle ces grammaires linéaires à droite. C'est cette contrainte qui traduit la mémoire bornée de l'automate : à tout instant, il n'y a qu'un seul non-terminal dans la forme dérivée, et il est tout à droite — il joue exactement le rôle de l'état courant.

Deux conséquences.

• L'inclusion est stricte : $S\to aSb\mid \epsilon$ place son non-terminal au milieu, ce qu'aucune grammaire linéaire à droite ne sait faire. C'est là qu'est le gain de puissance.
• La grammaire obtenue est non ambiguë — ce qui a été vérifié sur tous les mots jusqu'à la longueur $8$ —, et ce n'est pas un hasard : la dérivation est forcée par l'automate, qui est déterministe. Le déterminisme d'un automate donne la non-ambiguïté de la grammaire correspondante.

La grammaire a été comparée à l'automate sur les $1023$ mots de longueur au plus $9$ : accord complet.