Dérivations et arbres de dérivation

Dériver un mot à partir de l'axiome, dérivations gauche et droite, arbre de dérivation, grammaire ambiguë et levée de l'ambiguïté par les priorités.

Le programme, thème par thème

Le poids de chaque thème suit celui que lui donne l'examen.

Dérivation : de quoi s'agit-il ?
Voir la réponse
Suite de réécritures qui part de l'axiome et applique à chaque pas une règle de la grammaire, jusqu'à obtenir un mot sans non-terminal.
Un mot appartient au langage si et seulement s'il possède au moins une telle suite. On note chaque pas avec une flèche double : E ⇒ E + T.
Avec E → E + T | T, T → T * F | F, F → n, on dérive n + n * n à gauche. Quelle chaîne a-t-on après trois pas à partir de E ?
- F + T
- T + T
- n + T
- E + T * F
Voir la réponse
F + T
E ⇒ E + T ⇒ T + T ⇒ F + T. Le troisième pas réécrit le T de gauche (le plus à gauche) en F. T + T n'a que deux pas, n + T en a quatre, et E + T * F vient d'une dérivation droite.
Dans une dérivation …, on réécrit toujours le non-terminal le plus à gauche ; dans une dérivation …, le plus à droite.
Voir la réponse
Dans une dérivation gauche, on réécrit toujours le non-terminal le plus à gauche ; dans une dérivation droite, le plus à droite.
Les deux produisent le même arbre quand la grammaire n'est pas ambiguë : seul l'ordre des pas change.
Dérivation gauche : de quoi s'agit-il ?
Voir la réponse
Dérivation où chaque pas réécrit le non-terminal le plus à gauche de la chaîne courante.
Elle fixe l'ordre des réécritures : à un arbre de dérivation correspond une seule dérivation gauche (et une seule dérivation droite).