Écrire une grammaire – et vérifier qu'elle n'est pas ambiguë

1. Elle engendre $L$.

Tout mot engendré est dans $L$ : par induction, chaque règle ajoute autant de a que de b.

Tout mot de $L$ est engendré : par récurrence forte sur $|w|$. Si $w=\epsilon$, la troisième règle convient. Sinon, notons $h(u)=|u{|}_a-|u{|}_b$ la « hauteur ». On a $h(w)=0$. Supposons $w$ commençant par a — le cas symétrique se traite de même. Alors $h$ vaut $1$ après la première lettre et $0$ à la fin : soit $p$ le premier indice $>1$ où $h$ redevient $0$. La lettre en $p$ est nécessairement un b, et l'on écrit $w=aubv$ avec $u$ et $v$ de hauteur nulle et plus courts que $w$. L'hypothèse de récurrence les engendre.

Le décompte confirme : pour les longueurs $0,2,4,6,8$, la grammaire engendre $1,2,6,20,70$ mots, soit exactement les $\left(\genfrac{}{}{0ex}{}{2m}{m}\right)$ mots de $L$ — vérifié par énumération de tous les mots jusqu'à la longueur $8$.

2. Oui, elle est ambiguë, et le plus court témoin est abab, qui a deux arbres :

• $S\to aSbS$ avec le premier $S$ vide, le b en position $2$, et le dernier $S$ engendrant ab ;
• $S\to aSbS$ avec le premier $S$ engendrant ba, le b en position $4$, et le dernier $S$ vide.

Autrement dit, le b apparié au premier a n'est pas déterminé : la règle ne dit pas lequel des deux b.

Ce que l'exercice met en scène. On vérifie d'ordinaire qu'une grammaire engendre le bon langage, et l'on s'arrête là. C'est insuffisant : celle-ci est correcte au sens du langage et inutilisable telle quelle pour un compilateur. La correction d'une grammaire a donc deux volets, et le second se teste — il suffit de compter les arbres de tous les mots courts.

Pour la rendre non ambiguë, il faut fixer l'appariement, par exemple en exigeant que le b choisi soit le premier qui ramène la hauteur à zéro — c'est-à-dire en imposant au premier $S$ de la règle de rester de hauteur strictement positive. Cela demande deux non-terminaux de plus.