Probleme – Émonder une grammaire, et décider si son langage est vide

1. Les productifs. Un symbole est productif s'il dérive au moins un mot de terminaux. On calcule l'ensemble $P$ par point fixe croissant :

P <-- ensemble vide
répéter
    pour chaque règle A --> alpha
        si tous les non-terminaux de alpha sont dans P
            alors ajouter A à P
jusqu'à ce que P ne change plus

Un terminal compte pour productif : la condition « tous les non-terminaux de $\alpha$ sont dans $P$ » est vraie pour une règle entièrement terminale, ce qui amorce le calcul.

Terminaison. Variant : $|N|-|P|$, où $N$ est l'ensemble des non-terminaux. Chaque tour qui change quelque chose fait croître $P$ strictement, et $P\subseteq N$ est borné. Il y a donc au plus $|N|$ tours.

Correction, dans les deux sens.

• Tout élément de $P$ est productif : par récurrence sur le tour où il est ajouté. Si $A$ entre au tour $k$ par la règle $A\to \alpha$, chaque non-terminal de $\alpha$ était déjà dans $P$, donc dérive un mot de terminaux par hypothèse de récurrence ; on les concatène.
• Tout symbole productif finit dans $P$ : par récurrence sur la hauteur du plus petit arbre de dérivation d'un mot de terminaux à partir de $A$. Si cet arbre a pour racine $A\to \alpha$, chacun des non-terminaux de $\alpha$ a un sous-arbre strictement plus petit, donc entre dans $P$ avant $A$.

2. Les accessibles. Un symbole est accessible s'il apparaît dans une forme dérivée du symbole initial. C'est un simple parcours de graphe depuis $S$ (chapitre chap:parcours), dans le graphe où l'on met un arc de $A$ vers chaque non-terminal figurant dans un membre droit d'une règle de $A$. La correction est celle du parcours : on atteint exactement les sommets reliés à $S$ par un chemin.

3. Décider la vacuité. $L(G)=\varnothing$ si et seulement si le symbole initial n'est pas productif. C'est immédiat : $L(G)$ est l'ensemble des mots de terminaux dérivant de $S$, donc il est non vide exactement quand $S$ est productif.

Complexité. Écrit naïvement, le calcul de $P$ fait $|N|$ tours, chacun parcourant toutes les règles : $O(|N|\cdot \Vert G\Vert )$, où $\Vert G\Vert$ est la taille totale de la grammaire. On descend à $O(\Vert G\Vert )$ en tenant, pour chaque règle, un compteur des non-terminaux encore manquants et une file des symboles nouvellement productifs — c'est la même technique que le tri topologique.

Un exemple mesuré. Sur

$$S\to aA\mid B,A\to aA,B\to b,C\to cC\mid c,$$

le calcul donne $P=\{S,B,C\}$ et l'ensemble des accessibles $\{S,A,B\}$. La grammaire émondée est $S\to B$, $B\to b$, et son langage est $\{\text{b}\}$ — identique à celui de départ. Deux non-terminaux sur quatre étaient inutiles, pour deux raisons différentes.

4. La comparaison avec les automates. Elle est exacte, et instructive.

La vacuité est décidable des deux côtés, et pour la même raison : dans les deux cas, il suffit d'un calcul de point fixe sur un ensemble fini. C'est une bonne occasion de mesurer ce que « décidable » veut dire concrètement : la question porte sur une infinité de mots, et l'on y répond par un calcul fini, dont on sait borner la durée à l'avance.

Ce qui, en revanche, sépare les deux mondes. Pour les automates, on décide aussi l'équivalence et l'universalité. Pour les grammaires non contextuelles, ni l'une ni l'autre n'est décidable, non plus que l'ambiguïté. La vacuité est presque la seule question qui reste calculable — et c'est déjà la plus utile, car c'est elle qui repère les règles mortes d'une grammaire de compilateur.