Dériver un mot

Dériver un mot

Grammaires non contextuelles · niveau 2

É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.

Énoncé

Corrigé

Exercices semblables