Grammaires

Théorie des Langages Formels

Chapitre 7 : Grammaires

Florence Levé
[email protected]

Année 2014-2015

1/22
Grammaires

Reconnaître ou engendrer

Un automate peut être vu comme une machine permettant de

reconnaître des mots. On “entre” un mot dans la machine, et
en résultat, on a comme réponse “le mot appartient au
langage” ou “le mot n’appartient pas au langage”.

Avec une grammaire, on s’intéresse plus à la structure des

mots du langage pour expliquer comment ils se fabriquent.
Une fois qu’on a les “règles de fabrication” (appelées "règles de
production"), on peut engendrer tel ou tel mot.
Exemple : Phrase = Sujet + Verbe
Sujet = "L’étudiant" | "Le professeur"
Verbe = "écoute" | "enseigne"

2/22
Grammaires

Récursivité

Les langages peuvent contenir un nombre infini de mots, de

phrases. . . qui peuvent être exprimés par un nombre fini de
productions.
Pour cela, on utilise la répétition des éléments contenus dans
les règles de production de la grammaire : on construit les
éléments récursivement.
Exemple :
nombre = chiffre | chiffre nombre
chiffre = "0" | "1" | "2" |"3" | "4" | "5" | "6" | "7" | "8" |
"9"

3/22
Grammaires

Grammaire algébrique
Une grammaire algébrique s’appelle aussi grammaire hors
contexte ou non contextuelle (en anglais, context-free
grammar).
Une grammaire algébrique est un quadruplet G = (Σ, N, P, S)
où :
I Σ est un alphabet, dit alphabet des terminaux ;
I N est un alphabet, dit alphabet des non-terminaux ou des
v ariables, tel que N ∩ Σ = ∅ ;
I P est une partie finie de N × (Σ ∪ N)∗
Chaque élément de P est appelé une règle de production ;
I S est un élément de N appelé axiome de G (symbole initial).
Tous les mots de la grammaire peuvent être obtenus en
appliquant des règles de production successivement à partir de
l’axiome.
Remarques : en général, les lettres terminales sont notées par des
lettres minuscules ou des lettres grecques, et les lettres non
terminales sont notées par des lettres majuscules.
4/22
Grammaires

Exemple : les mots bien parenthésés

Décrivons le langage des mots bien parenthésés en ne nous

occupant que des parenthèses (le langage de Dyck).
Un mot bien parenthésé est :
un mot sans parenthèse (le mot vide ε puisqu’on ne considère
que le langage des parenthèses),
la concaténation de deux mots bien parenthésés : ( ) ( ),
une parenthèse ouvrante, un mot bien parenthésé, une
parenthèse fermante : ( ( ) ).

Si S représente une expression bien parenthésée, ces trois règles

peuvent s’écrire : S → ε, S → SS et S → (S).
Les lettres terminales sont ( et ) et S est une lettre non terminale,
qui est également l’axiome de la grammaire.

5/22
Grammaires

Exemple
Remarques.
Plutôt que de noter (X , u) une règle de production, on note
usuellement X → u.
Quand il existe plusieurs règles de production (X , u1 ), (X , u2 ),
. . . , (X , un ), on note usuellement X → u1 | u2 | . . . | un (le
symbole | signifiant “ou” dans ce contexte).

La grammaire des mots bien parenthésés peut donc se noter :

Gbp = ({(, )}, {S}, {(S, ε), (S, SS), (S, (S))}, S)
ou encore :
Gbp = ({(, )}, {S}, {S → ε | SS | (S)}, S).
Cette grammaire peut aussi s’écrire :
Gbp = ({(, )}, {S}, {S → ε | (S)S}, S).

6/22
Grammaires

Mots dérivés directement

Mot dérivé directement. Soient u et v deux mots sur Σ ∪ N.

Le mot v se dérive directement de u par la grammaire
algébrique G = (Σ, N, P, S) s’il existe des mots u1 et u2 et une
règle de production X → w tels que u = u1 Xu2 et v = u1 wu2 .

Exemple :
I Les mots ε, (S) et SS sont les seuls mots qui se dérivent
directement de S par la grammaire Gbp .

7/22
Grammaires

Mots dérivés

Mot dérivé. Soient u et v deux mots sur Σ ∪ N. Le mot v se

dérive de u par la grammaire algébrique G = (Σ, N, P, S) s’il
existe des mots w0 , w1 , . . . , wn tels que u = w0 , v = wn et
pour tout entier i (0 ≤ i < n), wi+1 se dérive directement de
wi .
Exemples : Les mots (((S)S)(S)S), (S)(S)S, (S)S et S se
dérivent de S par la grammaire Gbp .

8/22
Grammaires

Notation

Une dérivation s’écrit souvent :

u = w0 → w1 → w2 → . . . → wn = v
Par exemple : S → (S)S → (S)(S)S → ((S)S)(S)S

Remarque. On observera que si on prend n = 0, on peut avoir

v = u, et donc tout mot se dérive directement de lui-même.

9/22
Grammaires

Appartenance d’un mot au langage de la grammaire

Pour montrer qu’un mot appartient au langage, il faut et il
suffit de montrer qu’il s’obtient à partir des règles de
production de la grammaire (en commençant par l’axiome).
Par exemple, le mot (())() s’obtient par :

S → SS → (S)S
→ ((S))S
→ ((ε))S = (())S
→ (())(S)
→ (())(ε) = (())().

Chaque dérivation peut être représentée sous la forme d’un

arbre de dérivation.
10/22
Grammaires

Arbre de dérivation

Un arbre de dérivation est défini de la manière suivante :

I les sommets sont étiquetés par une lettre ou par ε, les feuilles
par une lettre terminale ou ε, les sommets internes par une
lettre non terminale ;
I un sommet interne étiqueté X a pour fils (dans cet ordre)
x1 , . . . , xn avec xi ∈ Σ ∪ N, si X → x1 . . . xn est une règle de
production de la grammaire.
Un arbre de dérivation est traditionnellement dessiné la racine
en haut. Sur un tel arbre dessiné, le mot dérivé s’obtient en
concaténant les étiquettes des feuilles de gauche à droite.

11/22
Grammaires

Exemple

Arbre de dérivation du mot (())() :

S

S S

( S ) ( S )

( S ) ε

ε
Remarque : deux dérivations peuvent être associées au même arbre
de dérivation (les règles de productions peuvent être appliquées
dans un ordre différent).

12/22
Grammaires

Autre exemple

Certains mots peuvent s’obtenir par plusieurs arbres de

dérivations, comme par exemple le mot : ()()().
S S

S S S S

( S ) S S S S ( S )

ε ( S ) ( S ) ( S ) ( S ) ε

ε ε ε ε

13/22
Grammaires

Langages algébriques

Le langage engendré par une grammaire algébrique

(Σ, N, P, S) est l’ensemble des mots de Σ∗ qui se dérive de S
par la grammaire.
Exemple : le langage des mots bien parenthésés est engendré
par la grammaire Gbp .

Un langage est dit algébrique s’il existe une grammaire

algébrique qui l’engendre.
Exemple : le langage des mots bien parenthésés est un langage
algébrique.

14/22
Grammaires

Exercice

Ecrire une grammaire permettant d’engendrer l’ensemble des

mots sur {a, b} ayant le même nombre d’occurrences de a que
de b.
Ecrire une grammaire permettant d’engendrer l’ensemble des
mots sur {a, b} ayant deux fois plus de a que de b.

15/22
Grammaires

Ambiguïté

Une grammaire est ambiguë s’il existe un mot qui admet deux
arbres de dérivations distincts.

Langage ambigu. Un langage est ambigu si toute grammaire

qui l’engendre est ambiguë.

Théorème : Le problème de déterminer si une grammaire est

ambiguë est indécidable (i.e. il n’est pas possible d’élaborer un
algorithme qui soit capable de dire, après un temps fini, si une
grammaire que l’on lui soumet est ambiguë ou non.).
Remarque : on peut toutefois montrer qu’une grammaire
donnée est ambiguë en donnant un mot engendré par cette
grammaire admettant deux arbres de dérivations distincts...

16/22
Grammaires

Dérivation la plus à gauche

On peut décider de toujours remplacer en premier la lettre non

terminale la plus à gauche d’une expression.
Cela permet de simplifier la recherche d’une dérivation entre
deux mots, de montrer plus facilement qu’il n’y a pas de
dérivation entre deux mots, ou qu’il n’y en a qu’une seule...

17/22
Grammaires

Dérivation la plus à gauche

Lemme : Soit G = (Σ, N, P, S) une grammaire. Si u1 , u2 , v

sont trois mots tels que u1 u2 se dérivent en v , alors il existe
des mots v1 et v2 tels que v = v1 v2 , v1 se dérive de u1 , et v2
se dérive de u2 .
Soit G = (Σ, N, P, S) une grammaire. Une dérivation gauche
d’un mot v en un mot u est une suite de mots w0 , . . . , wn tels
que u = w0 , v = wn et pour tout entier i, 0 ≤ i < n,
wi = ui Xi ui0 et wi+1 = ui vi ui0 avec ui ∈ Σ∗ , (Xi → vi ) ∈ P,
ui0 ∈ (Σ ∪ N)∗ .
Proposition : Soit G = (Σ, N, P, S) une grammaire. Pour tout
mot u et v sur Σ ∪ N, si v se dérive de u alors v se dérive de u
par une dérivation gauche.

18/22
Grammaires

Grammaires et langages reconnaissables

Proposition : L’union, le produit et l’étoile de langages

algébriques sont des langages algébriques.
Pour tout langage fini, on peut donner facilement une
grammaire engendrant le langage.
Donc tout langage reconnaissable est un langage algébrique.
La réciproque est fausse.

19/22
Grammaires

Grammaires linéaires

Une grammaire G = (Σ, N, P, S) est dite linéaire gauche si

toutes les règles de production appartiennent à
N × (NΣ∗ ∪ Σ∗ ).

Une grammaire G = (Σ, N, P, S) est dite linéaire droite si

toutes les règles de production appartiennent à
N × (Σ∗ N ∪ Σ∗ ).

Une grammaire G = (Σ, N, P, S) est dite linéaire si toutes les

règles de production appartiennent à N × (Σ∗ NΣ∗ ∪ Σ∗ ).
Proposition : Sont équivalents pour un langage L :
1. L est reconnaissable,
2. L est engendré par une grammaire linéaire gauche,
3. L est engendré par une grammaire linéaire droite.

20/22
Grammaires

Idée de la preuve : 1) ⇒ 2)
Si un langage L est reconnaissable, nous avons vu précédemment
comment définir des équations définissant le langage. Ces équations
peuvent être vues commes des règles de grammaires linéaires
droites.

A B
a

b b
a

D C

La grammaire associée est :

A → aB | bD
B → bC
C → aA
D →ε
21/22
Grammaires

Idée de la preuve : 2) ⇒ 1)

Réciproquement, si nous avons une grammaire linéaire gauche,

grâce au lemme d’Arden, nous pouvons donner une expression
régulière représentant le langage engendré. Ce langage est donc
reconnaissable.
Remarques :
Pour l’équivalence avec grammaire linéaire droite, il faut "lire"
l’automate à l’envers.
Attention : un langage engendré par une grammaire linéaire
n’est pas nécessairement reconnaissable.

22/22