Symboles inutiles

Exercice · niveau 2 · informatique (MP2I/MPI), chapitre 30 — Grammaires non contextuelles

Énoncé

Soit la grammaire de symbole initial $S$ sur ${a, b, c}$ :

$S \to a A ∣ B, A \to a A, B \to b, C \to c C ∣ c .$

Quel est le langage engendré ?
Identifier les symboles productifs et les symboles accessibles.
Écrire la grammaire émondée.

Corrigé

1. $L (G) = {b}$ . Un seul mot.

2. Deux notions, indépendantes, et qui se calculent chacune par un point fixe.

Productif : le symbole engendre au moins un mot de terminaux. On part des non-terminaux ayant une règle entièrement terminale, et l'on ajoute tant qu'on peut. Ici $B$ (par $B \to b$ ) et $C$ (par $C \to c$ ), puis $S$ (par $S \to B$ ). $A$ n'est pas productif : sa seule règle $A \to a A$ ne termine jamais. Productifs $= {S, B, C}$ .
Accessible : le symbole apparaît dans une forme dérivée du symbole initial. Parcours depuis $S$ : on atteint $A$ (par $S \to a A$ ) et $B$ (par $S \to B$ ). $C$ n'est pas accessible. Accessibles $= {S, A, B}$ .

$A$ est accessible mais stérile ; $C$ est fertile mais inatteignable. Les deux défauts sont bien distincts.

3. On supprime d'abord les non-productifs — et toutes les règles où ils figurent, donc $S \to a A$ disparaît aussi — puis les inaccessibles :

$S \to B, B \to b .$

ImportantL'ordre des deux nettoyages n'est pas indifférent

Il faut supprimer les non-productifs d'abord, les inaccessibles ensuite. Sur

$S \to a ∣ A B, A \to a, B \to B b,$

$B$ n'est pas productif, et tout est accessible.

Productifs puis accessibles : on retire $B$ , donc la règle $S \to A B$ , donc $A$ devient inaccessible et disparaît. Il reste $S \to a$ : correct.
Accessibles puis productifs : rien n'est inaccessible, on ne retire donc que $B$ ; il reste $S \to a$ et $A \to a$ , où $A$ n'est plus accessible. La grammaire contient encore un symbole inutile.

Supprimer un symbole peut en rendre un autre inaccessible ; cela ne peut jamais rendre un symbole non productif. Le sens de l'implication fixe l'ordre.

Le parallèle avec l'émondage d'un automate est exact : « productif » est le co-accessible, « accessible » est l'accessible, et l'on parcourt dans les deux sens.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.