Théorie des langages

Ce matériel couvre les notions fondamentales de la théorie des langages, en particulier les grammaires, leurs types, la dérivation, les arbres de dérivation, ainsi que les concepts d'ambiguïté et d'indépendance du contexte. Il s'adresse aux étudiants en informatique ou en linguistique formelle souhaitant comprendre la génération des langages par des grammaires formelles.

La dérivation

Une dérivation d’un mot w à partir d’une grammaire G avec le symbole de départ S, notée S * w, est une application successive d’un ensemble de règles de production en partant du symbole de départ S.

L’application d’une règle de la forme u → v consiste à remplacer la sous-chaîne u par la sous-chaîne v.

Langage généré par une grammaire

Soit G = (V, T, S, R) une grammaire. Le langage L(G) généré par G est l’ensemble des mots dérivés à partir de S :

L(G) = { w ∈ T* | S * w }

Types de grammaires

Grammaire non contextuelle (hors contexte)

Une grammaire G = (V, T, S, R) est dite non contextuelle si les règles de production sont de la forme :

A → u

où A ∈ V et u ∈ (T + V)*.

Exemple :

G = ({S}, {a, b}, S, R) avec R = { S → aSb | ɛ }

Grammaire dépendante du contexte

Une grammaire G = (V, T, S, R) est dite dépendante du contexte si elle inclut au moins une règle de production qui admet à gauche plus d’un non terminal.

Exemple :

G = ({S}, {a, b}, S, R) avec
R = {
  S → AB,
  A → aAb | ɛ,
  B → cB | ɛ
}

Le langage généré est :

L(G) = { w ∈ {a,b}* | w = a^n b^n c^m, n ≥ 0, m ≥ 0 }

Langages indépendants du contexte

Un langage est dit indépendant du contexte s’il existe une grammaire non contextuelle qui le génère.

Exemples :

• a*b* appartient aux langages réguliers
• {a^n b^n, n ≥ 0} appartient aux langages indépendants du contexte
• {a^n b^n c^m, n ≥ 0, m ≥ 0} appartient aux langages dépendants du contexte

Arbre de dérivation

À chaque dérivation d’un mot à partir d’une grammaire est associé un arbre appelé arbre de dérivation (ou arbre syntaxique).

C’est un arbre dont la racine porte l’étiquette S (axiome de la grammaire). Pour chaque nœud portant l’étiquette X, on construit des fils Y1, Y2, …, Yn si une règle de production de la forme :

X → Y1 Y2 … Yn

a été appliquée.

Le mot dérivé apparaît dans les feuilles de l’arbre en les parcourant de gauche à droite.

Exemple d’arbre de dérivation

Soit la grammaire :

G = ({S}, {a}, S, { S → SS | a })

Pour le mot w = aa :

• Dérivation 1 : S → SS → aS → aa
• Dérivation 2 : S → SS → Sa → aa

Pour le mot w = aaa :

• Dérivation 1 : S → SS → aS → aSS → aaS → aaa
• Dérivation 2 : S → SS → SSS → SSa → Saa → aaa

Les deux dérivations sont différentes, ce qui montre la possibilité de plusieurs arbres de dérivation pour un même mot.

Dérivation la plus à gauche

La dérivation la plus à gauche consiste à remplacer en premier le non terminal le plus à gauche par la partie droite d’une règle de production.

Exemple

Soit la grammaire :

G = ({Exp}, {(,), id, nb}, Exp, R) avec
R = { Exp → Exp + Exp | id | nb | (Exp) }

Pour le mot :

w = (id + nb) + id

La dérivation la plus à gauche est :

Exp
→ Exp + Exp
→ (Exp) + Exp
→ (id + Exp) + Exp
→ (id + nb) + Exp
→ (id + nb) + id

Dérivation la plus à droite

La dérivation la plus à droite consiste à remplacer en premier le non terminal le plus à droite par la partie droite d’une règle de production.

Exemple

Avec la même grammaire que précédemment, pour le mot :

w = (id + nb) + id

La dérivation la plus à droite est :

Exp
→ Exp + Exp
→ Exp + id
→ (Exp) + id
→ (Exp + Exp) + id
→ (Exp + nb) + id
→ (id + nb) + id

Grammaire ambigüe

Une grammaire G est dite ambigüe s’il existe pour un même mot au moins deux dérivations la plus à gauche différentes, donc deux arbres de dérivation différents. Sinon, G est dite non ambigüe.

Exemple de grammaire ambigüe

Soit la grammaire :

G = ({A, S}, {a, b}, S, R) avec
R = {
  S → aAb | a | abSb,
  A → bS
}

Pour le mot abab :

• Dérivation 1 : S → aAb → abSb → abab
• Dérivation 2 : S → abSb → abab

Le mot abab possède deux dérivations la plus à gauche différentes, donc G est ambigüe.

Exercice

Soit la grammaire :

G = ({S}, {a, b}, S, R) avec
R = { S → SaSaS | bS | ɛ }

1. Quel est le langage généré ?

Le langage est :

L(G) = { w ∈ {a, b}* | le nombre de a dans w est pair, c’est-à-dire |w|_a = 2k, k ≥ 0 }

2. Montrer que G est ambigüe.

Pour le mot baa, il existe deux dérivations la plus à gauche différentes :

• Dérivation 1 : S → SaSaS → bSaSaS → baSaS → baaS → baa
• Dérivation 2 : S → bS → bSaSaS → baSaS → baaS → baa

Donc G est ambigüe.

3. Construire une grammaire G’ équivalente à G, non ambigüe.

Pour cela, il faut d’abord construire un automate fini déterministe reconnaissant L(G), puis convertir cet automate en une grammaire G’ :

G' = ({S, A}, {a, b}, S, R') avec
R' = {
  S → aA | bS | ɛ,
  A → bA | aS
}

Glossaire des termes clés

• Dérivation : Processus d’application successive des règles de production d’une grammaire pour obtenir un mot à partir du symbole de départ.
• Langage généré : Ensemble des mots dérivés à partir du symbole de départ d’une grammaire.
• Grammaire non contextuelle : Grammaire dont les règles ont la forme A → u, avec A un non terminal et u une chaîne de terminaux et non terminaux.
• Grammaire dépendante du contexte : Grammaire avec au moins une règle ayant plusieurs non terminaux à gauche.
• Langage indépendant du contexte : Langage généré par une grammaire non contextuelle.
• Arbre de dérivation : Arbre représentant la dérivation d’un mot, avec racine le symbole de départ et feuilles les symboles terminaux du mot.
• Dérivation la plus à gauche : Dérivation où l’on remplace toujours le non terminal le plus à gauche en premier.
• Dérivation la plus à droite : Dérivation où l’on remplace toujours le non terminal le plus à droite en premier.
• Grammaire ambigüe : Grammaire pour laquelle un même mot peut avoir plusieurs dérivations la plus à gauche différentes.

Points clés à retenir

• La dérivation est la base pour générer des mots à partir d’une grammaire.
• Les grammaires peuvent être classées selon la forme de leurs règles : non contextuelles ou dépendantes du contexte.
• Un langage est indépendant du contexte s’il est généré par une grammaire non contextuelle.
• L’arbre de dérivation visualise la structure de la dérivation d’un mot.
• Les dérivations la plus à gauche et la plus à droite sont des stratégies de dérivation différentes.
• Une grammaire ambigüe peut générer plusieurs arbres de dérivation différents pour un même mot.
• Il est possible de transformer une grammaire ambigüe en une grammaire équivalente non ambigüe via un automate fini déterministe.