Introduction aux grammaires

Ce matériel couvre les notions fondamentales des grammaires formelles, leur classification selon la hiérarchie de Chomsky, ainsi que des exemples et exercices pour mieux comprendre leur fonctionnement. Il s'adresse aux étudiants en informatique, linguistique formelle ou mathématiques intéressés par la théorie des langages formels.

Définition et exemple de grammaire

Une grammaire est un quadruplet G = (V, T, P, S) où :

• V est l’ensemble des variables (ou symboles non-terminaux) ;
• T est l’ensemble des terminaux ;
• P est l’ensemble des règles de production, où chaque règle est une relation de la forme (V ∪ T)* V (V ∪ T)* → (V ∪ T)* ;
• S ∈ V est le symbole de départ.

Exemple :

Soit la grammaire G avec :

• V = {S}
• T = {a, b, e}
• Règles P :

S → aSbS
S → bSaS
S → e

Le symbole S est la seule variable et aussi le symbole de départ.

Arbre de dérivation

Pour le mot abeaebe, l'arbre de dérivation selon G est :

S
├─ a
├─ S
├─ b
├─ a
├─ b
├─ S
├─ e
├─ S
├─ e
├─ S
├─ e

La dérivation à gauche est :

S → aSbS → abSaSbS → abeaSbS → abeaebS → abeaebe

On conclut que abeaebe appartient au langage L(G).

Hiérarchie de Chomsky

La hiérarchie de Chomsky classe les grammaires en quatre types selon les restrictions sur leurs règles :

• Classe 0 : grammaires non restreintes
  - Pas de restrictions sur la forme des règles.
  - Langages reconnus par une machine de Turing.
• Classe 1 : grammaires context-sensitive
  - Règles de la forme #A# → #β#, avec β ∈ (V ∪ T)+ et #, β ∈ (V ∪ T)*.
  - La règle S → ε est possible si S n’apparaît dans aucun membre de droite.
  - Langages reconnus par une machine de Turing non déterministe avec ruban de longueur bornée.
• Classe 2 : grammaires context-free
  - Règles de la forme A → β, avec A ∈ V et β ∈ (V ∪ T)*.
  - Langages reconnus par un automate à pile non déterministe.
• Classe 3 : grammaires régulières
  - Grammaires linéaires droites : règles du type A → wB ou A → w, avec w ∈ T*.
  - Grammaires linéaires gauches : règles du type A → Bw ou A → w.
  - Langages reconnus par un automate fini.

Exemples de grammaires

Grammaire context-free G' :

1. S → aSb
2. S → ε

Grammaire context-sensitive G :

1. S → ABS
2. BA → AB
3. BS → b
4. Bb → bb
5. Ab → ab
6. Aa → aa

Les langages générés par G et G' sont identiques : L(G) = L(G') = {a^n b^n}. Bien que G soit context-sensitive, le langage est context-free.

Exercices et solutions

Exercice 1

Décrivez en français les langages générés par les grammaires suivantes, et donnez leur type :

1. S → abcA | Aabc
   A → ε
   Aa → Sa
   cA → cS
   

2. S → 0 | 1 | 1S
   

3. S → a | *SS | +SS
   

Solution 1

• 1. Grammaire non restreinte générant toutes les suites de "abc".
• 2. Grammaire linéaire droite générant toutes les suites de "1" éventuellement terminées par un "0", ou bien la chaîne "0".
• 3. Grammaire context-free générant toutes les expressions arithmétiques en notation polonaise utilisant la somme (+) et le produit (*) sur la variable "a".

Exercice 2

Soit la grammaire G :

S → AB
A → Aa | bB
B → a | Sb

Questions :

• Cette grammaire est-elle régulière ?
• Donnez l'arbre de dérivation pour les mots baabaab, bBABb et baSb.
• Donnez les dérivations gauche et droite de baabaab.

Solution 2

Cette grammaire est context-free mais pas régulière. En effet, une grammaire régulière ne peut pas avoir à la fois des règles de la forme A → αB et A → Bβ.

Arbres de dérivation (extraits)

S
├─ A
│  ├─ b
│  └─ B
│     └─ ...
└─ B
   └─ ...

Les arbres pour bBABb et baSb suivent une structure similaire avec des expansions selon les règles.

Dérivation gauche de baabaab :

S → AB → AaB → bBaB → baaB → baaSb → baaABb → baabBBb → baabaBb → baabaab

Dérivation droite de baabaab :

S → AB → ASb → AABb → AAab → AbBab → Abaab → Aabaab → bBabaab → baabaab

Exercice 3

Écrivez une grammaire context-free générant toutes les chaînes de a et b telles qu'il y a plus de a que de b. Testez-la sur baaba en donnant une dérivation.

Écrivez une grammaire context-sensitive générant toutes les chaînes de a, b et c ayant le même nombre de a, b et c, quel que soit l'ordre. Donnez la dérivation de cacbab.

Solution 3

Grammaire context-sensitive :

S → ABCS | ε
AB → BA
AC → CA
BA → AB
BC → CB
CA → AC
CB → BC
A → a
B → b
C → c

Dérivation de cacbab :

S → ABCS → ABCABCS → ABCABC → ACBABC → CABABC → CABACB → CABCAB → CACBAB → cACBAB → caCBAB → cacBAB → cacbAB → cacbaB → cacbab

Exercice 4

1. Écrivez une grammaire context-free pour les langages 0^i 1^n 2^n et 0^n 1^n 2^i, avec n,i > 0.

2. Montrez que l'intersection de deux langages context-free n'est pas nécessairement context-free.

Solution 4

S → AB

A → 0A | 0
A → 0A1 | 01

B → 1B2 | 12
B → 2B | 2

Les langages :

• L1 = {0^i 1^n 2^n | n > 0, i > 0} est context-free.
• L2 = {0^n 1^n 2^i | n > 0, i > 0} est context-free.
• L1 ∩ L2 = {0^n 1^n 2^n | n > 0} n'est pas nécessairement context-free.

Exemple avec L1 = ∅ et L2 = {0^n 1^n | n > 0}, leur intersection est ∅ qui est context-free.

Glossaire des termes clés

• Grammaire : quadruplet (V, T, P, S) définissant un langage formel.
• Variables (symboles non-terminaux) : symboles utilisés dans les règles de production pour générer des chaînes.
• Terminaux : symboles finaux qui apparaissent dans les chaînes du langage.
• Règles de production : transformations autorisées pour passer d'une chaîne à une autre.
• Symbole de départ : variable à partir de laquelle commence la génération des chaînes.
• Dérivation : suite d'applications de règles de production pour obtenir une chaîne.
• Arbre de dérivation : représentation arborescente des étapes de dérivation.
• Hiérarchie de Chomsky : classification des grammaires en quatre classes selon leurs restrictions.
• Grammaire non restreinte (Classe 0) : aucune restriction sur les règles.
• Grammaire context-sensitive (Classe 1) : règles où le contexte autour d'un symbole influence la production.
• Grammaire context-free (Classe 2) : règles où un seul symbole non-terminal est remplacé indépendamment du contexte.
• Grammaire régulière (Classe 3) : règles très restreintes, correspondant aux langages réguliers.
• Automate fini : machine reconnaissant les langages réguliers.
• Automate à pile : machine reconnaissant les langages context-free.
• Langage : ensemble de chaînes générées par une grammaire.

Points clés à retenir

• Une grammaire formelle est définie par ses variables, terminaux, règles et symbole de départ.
• La hiérarchie de Chomsky classe les grammaires selon la complexité de leurs règles et des langages qu'elles génèrent.
• Les grammaires context-free sont un cas important, reconnaissables par des automates à pile.
• Les langages réguliers sont les plus simples, générés par des grammaires régulières et reconnus par des automates finis.
• L'intersection de deux langages context-free n'est pas forcément context-free.
• Les exercices illustrent la construction et l'analyse de grammaires selon leur type et les langages qu'elles génèrent.