3. Génération de chaînes, fonctionnement et dérivation

Une grammaire G est peut être utilisée soit pour générer les phrases du langage L(G) soit pour déterminer si une phrase donnée appartient ou non au langage L(G) :

• La génération consiste à produire des chaînes de symboles par application des règles de la grammaire à partir de son axiome S.
• La vérification (l'analyse) consiste à retrouver la succession d'applications de règles qui a permis d'obtenir un mot en partant de l'axiome S.

On appelle application de règle, une dérivation directe. On étend cette notion à des suites finies d'applications de règles par les définitions qui suivent.

Notations et terminologie : On écrit ⇒ pour =G⇒ quand il n'y a pas d'ambigüité sur la grammaire et =R⇒ pour désigner explicitement la règle utilisée. On adopte en outre les conventions suivantes pour les dérivations, où a est la première chaîne de la dérivation et b la dernière :

• a =n⇒ b désigne une dérivation de longueur n.
• a =*⇒ b désigne une dérivation de longueur quelconque. Autrement dit, =*⇒ est la fermeture réflexive et transitive de =G⇒.
• a =+⇒ b désigne une dérivation de longueur supérieure à 1. Autrement dit, =+⇒ est la fermeture transitive de =G⇒.
• Si a =*⇒ b, on dit alors que a engendre b ou, symétriquement, que b dérive de a. Si de plus a =+⇒ b, on dit "engendre" (resp. "dérive") "de façon non triviale".

Pour reprendre les grammaires précédentes, nous avons les dérivations suivantes :

• G₀ : S ⇒ 0X1 ⇒ 00X11 ⇒ 000X111 ⇒ 000111
• G₁ : S ⇒ 0X1 ⇒ 00X11 ⇒ 000111
• G₂ : S ⇒ 0S1 ⇒ 00S11 ⇒ 000111
• G₃ : S ⇒ 0S ⇒ 00S ⇒ 000X ⇒ 0001X ⇒ 00011X ⇒ 000111

En conséquence de ces définitions, les formes sententielles d'une grammaire sont exactement les chaînes que l'on peut dériver à partir de son axiome S. On peut donc proposer une nouvelle définition d'une langage engendré par une grammaire, équivalente à la précédente.

Cette définition n'est pas très différente de la précédente, mais elle permet de manipuler explicitement les dérivations, ce qui est pratique pour certaines démonstrations.

Si l'on revient sur l'exemple précédent, on peut maintenant montrer que le langage de la grammaire G₀ coïncide exactement avec {0ⁿ1ⁿ | n ≥ 1}. Il faut pour cela montrer une double inclusion : {0ⁿ1ⁿ | n ≥ 1} ⊆ L(G₀) et L(G₀) ⊆ {0ⁿ1ⁿ | n ≥ 1}. Démonstration.

On a donc établi et illustré la façon dont une grammaire définit un langage. Il peut arriver qu'un même langage L soit atteint par deux grammaires différentes.

Par exemple, soit la grammaire G₄=({0, 1}, {S, X}, S, R) avec R :

• R1 : S → 0X1 ;
• R2 : X → 0X1 ;
• R3 : X → ε.

On pourrait montrer que cette grammaire définit le même langage que G₀, c'est-à-dire L(G₄)={aⁿbⁿ | n ≥ 1}=L(G₀), par une démonstration du même type que la précédente. Autrement dit, G₀ et G₄ sont équivalentes (il en est de même avec G₁ et G₂).