Dériver un mot

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

Énoncé

On reprend la grammaire du programme : $S \to T S ∣ c$ et $T \to a S b$ , sur ${a, b, c}$ .

Donner la dérivation à gauche de acbc, puis celle de aacbcbc.
Dessiner l'arbre d'analyse de acbc.
Combien d'étapes compte une dérivation ? Que compte-t-on au juste ?

Corrigé

1. On remplace à chaque fois le non-terminal le plus à gauche :

$S \Rightarrow T S \Rightarrow a S b S \Rightarrow a c b S \Rightarrow a c b c .$

$S \Rightarrow T S \Rightarrow a S b S \Rightarrow a T S b S \Rightarrow aa S b S b S \Rightarrow aa c b S b S \Rightarrow aa c b c b S \Rightarrow aa c b c b c .$

2. L'arbre d'analyse de acbc :

3. Les deux dérivations comptent quatre étapes pour acbc et sept pour aacbcbc. Une étape est une application de règle, donc un nœud interne de l'arbre. Le nombre d'étapes ne dépend donc pas de l'ordre choisi : c'est une propriété de l'arbre, pas de la dérivation.

La distinction qui compte. La dérivation est une suite, l'arbre est une structure. Plusieurs dérivations donnent le même arbre — elles ne diffèrent que par l'ordre des remplacements. C'est pourquoi l'ambiguïté se définit sur les arbres et non sur les dérivations : deux dérivations distinctes ne prouvent rien, deux arbres distincts prouvent tout.

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.