Notes de cours - Partie 1

Langages formels
Frédéric Blanqui (INRIA)

version du 28/09/20

Retrouvez les informations sur le cours, les notes de cours et les TDs sur:
http://rewriting.gforge.inria.fr/lsf.html.

Dans ce cours, nous nous intéressons à différentes manières de définir des

langages pour représenter des données (e.g. XML) ou des programmes (e.g. C,
Java, OCaml), et comment vérifier qu’un fichier est bien un fichier XML ou un
programme C, Java, etc. sans erreurs syntaxiques.
Nous verrons plusieurs manières de définir des langages: avec une grammaire
(nous ne considérons que des grammaires dites algébriques ou hors-contextes),
des “machines” (automate ou automate à pile), ou une “expression régulière”.
Dans le 1er cours, nous introduirons la notion de grammaire algébrique et
établirons un certain nombre de propriétés fondamentales des grammaires al-
gébriques et de la classe des langages définissables par une grammaire algébrique.
Nous verrons également un certain nombre de transformations permettant de
simplifier la présentation d’une grammaire ou de la mettre sous une forme par-
ticulière.
Dans le 2e cours, nous introduirons la notion d’automate. Nous verrons que
l’analyse syntaxique d’un langage défini par une forme très simple de gram-
maire dite linéaire peut être implémentée de manière très efficace en utilisant
un automate (cela fera l’objet d’un TP).
Dans le 3e cours, nous verrons comment minimiser le nombre d’états d’un
automate. Nous verrons également que les automates avec ε-transitions ne sont
pas plus puissants que les automates standards, et quelles sont les propriétés de
la classe des langages reconnaissables par automate.
Dans le 4e cours, nous introduirons la notion d’expression régulière. Nous
verrons alors que grammaires linéaires, automates et expressions régulières sont
en fait équivalents et définissent la même classe de languages, mais que ces trois
techniques sont limitées: elles ne permettent pas de traiter les langages avec
parenthèses.
C’est ainsi que, dans le 5e et dernier cours, nous considérons la classe des
langages dits LL(k) qui peuvent être analysés efficacement en utilisant une forme
plus puissante de machine: un automate à pile.

1
1 Mots et langages
Un alphabet Σ est un ensemble fini quelconque dont les éléments sont appelés
lettres. Par exemple, Σ = {a, b, c, . . . , 0, 1, . . . , +, ∗, (, . . .}.
Un mot u est une suite finie de lettres juxtaposées (un fichier XML ou C
peut être vu comme un mot sur l’alphabet des caractères ASCII). Par exemple,
aac est un mot sur Σ = {a, b, c}. La longueur d’un mot est le nombre de lettres
qu’il contient. Par exemple, aac est de longueur 3. L’unique mot de longueur
nulle est noté ε et appelé le mot vide. L’ensemble des mots sur Σ est noté Σ∗ .
La concaténation d’un mot a1 . . . ap et d’un mot b1 . . . bq est le mot a1 . . . ap b1
. . . bq .
Remarque: La concaténation est une opération associative ((uv)w = u(vw)
pour tous mots u, v, w) ayant ε comme élément neutre (uε = εu = u pour tous
mots u). Muni de la concaténation, Σ∗ est ainsi un monoïde.
On peut itérer la concaténation d’un mot: u répété n fois est noté un . Par
récurrence, u0 = ε et un+1 = uun .
Un mot u est un facteur d’un mot v si v est de la forme xuy avec x, y des
mots. C’est un préfixe (resp. suffixe) si, de plus, x = ε (resp. y = ε).
Un language est un ensemble de mots, c’est-à-dire, une partie de Σ∗ .
On peut étendre les opérations sur les mots aux langages. Si L1 et L2 sont
deux langages sur le même alphabet Σ, alors L1 L2 = {u1 u2 ∈ Σ∗ |u1 ∈ L1 , u2 ∈
L2 }. Si L est un langage, soit Ln le langage des puissances de n d’un mot de L:
L0 = {ε} et Ln+1 = LLn . On note le langage de toutes les puissances possibles
d’un mot de L par: [
L∗ = Ln .
n∈N

C’est le plus petit langage clos par concaténation et contenant L ∪ {ε}.

2 Grammaires
Une manière de définir un language est d’utiliser une grammaire.
Une grammaire G est un quadruplet (Σ, N , R, S) où Σ est un alphabet (fini)
de terminaux, N est un alphabet (fini) de non-terminaux contenant S (non-
terminal de départ), et R est un ensemble fini de régles l → r où l, r ∈ (Σ ∪ N )∗ .
Une règle de la forme X → ε est dite une ε-règle. Une règle de la forme
X → Y est dite unaire.
Un mot u se réécrit (en une étape) en v, noté u →G v (ou simplement u → v
s’il est clair de quelle grammaire il s’agit), si u est de la forme xly avec x, y ∈ Σ∗ ,
v est de la forme xry et l → r ∈ R.
On note par u →∗ v si u se réécrit en v en n ≥ 0 étapes. On dit alors que u
se réduit en v. Par exemple, avec R = {S → 1, S → 2, S → S + S, S → S ∗ S},
noté plus simplement {S → 1 | 2 | S + S | S ∗ S}, nous avons la réduction
suivante (en soulignant le non-terminal réécrit à chaque étape):

S →S+S →1+S →1+S∗S →1+2∗S →1+2∗2 (1)

2
 La relation →∗ est la clôture réflexive et transitive de →, c’est-à-dire, la plus
petite relation reflexive et transitive contenant →. Si on définit →0 comme la
relation égalité et →n la réécriture en n étape (→n+1 =→→n ), alors
[
→∗ = →n .
n≥0

On note par →+ = n≥1 →n la clôture transitive de →.

S
Le langage engendré par G à partir d’un mot u ∈ (Σ ∪ N )∗ est l’ensemble
des mots de Σ∗ vers lesquels u peut se réécrire:

LG (u) = {v ∈ Σ | u →∗ v}.

Nous définissons alors le langage engendré par G, L(G), comme étant LG (S).
Il peut exister de nombreuses grammaires différentes pour un même langage.
Deux grammaires G1 et G2 sont dites équivalentes si elles engendrent le même
langage.
Deux grammaires équivalentes peuvent avoir des propriétés très différentes.
On aura donc parfois intérêt à transformer une grammaire en une autre gram-
maire ayant de meilleures propriétés.

Exemples de grammaires:
• Grammaire Yacc d’ANSI C:
https://www.lysator.liu.se/c/ANSI-C-grammar-y.html
• Grammaire de C11 (Annex A, p. 476):
http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf
• Grammaire de Python 3.7:
https://docs.python.org/3/reference/grammar.html
• Grammaire d’OCaml 4.07:
https://caml.inria.fr/pub/docs/manual-ocaml-4.07/language.html
• Liste de grammaires ANTLR:
https://github.com/antlr/grammars-v4

3 Grammaires algébriques
Une grammaire est dite algébrique (ou hors-contexte ou encore de type 2) si
toutes les règles sont de la forme X → u avec X ∈ N . Dans la suite, nous ne
considérons que des grammaires algébriques.
Un langage L est algébrique s’il existe une grammaire algébrique G telle que
L = L(G).
Pour toute grammaire (y compris les grammaires non algébriques), si a →p a0
et b →q b0 , alors ab →p+q a0 b0 . Cette propriété peut-être inversée quand la
grammaire est algébrique:

3
Lemme 1 Avec une grammaire algébrique, si ab →n c, alors il existe a0 , b0 , p, q
tels que c = a0 b0 , n = p + q, a →p a0 et b →q b0 .
Preuve. Par récurrence sur n. Le cas n = 0 est immédiat. Si ab → c
alors, comme la grammaire est algébrique, il existe α, X, β, r tels que ab = αXβ
et c = αrβ. Soit le X est dans a, c’est-à-dire, β = α0 b, et il suffit de prendre
p = 1, a0 = αrα0 , q = 0 et b0 = b. Soit le X est dans b, c’est-à-dire, α = aβ 0 , et
il suffit de prendre p = 0, a0 = a, q = 1 et b0 = β 0 rβ. Ainsi, le cas n ≥ 1 suit
facilement par hypothèse de récurrence. 

Avec une grammaire algébrique, l’ensemble des mots que l’on peut engen-
drer à partir de ab est la concaténation de l’ensemble des mots que l’on peut
engendrer à partir de a et de l’ensemble des mots que l’on peut engendrer à
partir de b, qui sont indépendants l’un de l’autre:

Corollaire 1 Si G est une grammaire algébrique, alors LG (ab) = LG (a)LG (b).

De plus, la longueur de la réduction pour aller de a à a0 , ou de b à b0 , n’est pas
plus grande que celle pour aller de ab à a0 b0 (c’est même une sous-réduction),
ce qui peut être utile quand on raisonne par récurrence sur la longueur des
réductions.
Remarquons enfin que l’ordre de réduction des non-terminaux n’a pas d’im-
portance. Ainsi, dans les grammaires algébriques, on peut se limiter à une
stratégie particulière de dérivation, par exemple →g (respectivement →d ) la
relation consistant à réécrire le non-terminal le plus à gauche (respectivement à
droite). Les langages reconnus en utilisant →, →g ou →d sont identiques:

Lemme 2 Si G est une grammaire algébrique, alors L(G) = Lg (G) = Ld (G)

où Lg (G) = {u ∈ Σ∗ | S →∗g u} et Ld (G) = {u ∈ Σ∗ | S →∗d u}.

Preuve. Détaillons le cas de Lg (G). La preuve pour Ld (G) est similaire.

Nous avons Lg (G) ⊆ L(G) puisque →g ⊆ →. Montrons maintenant que, si
X ∈ Σ ∪ N et X →n u ∈ Σ∗ , alors X →ng u, par récurrence sur n. Si n = 0,
c’est immédiat. Supposons alors n > 0. Alors, X →g x1 . . . xk →n−1 u. Ainsi, il
existe u1 , . . . , uk et n1 , . . . , nk tels que u = u1 . . . uk , xi →ni ui et n−1 = Σki=1 ni .
Par hypothèse de récurrence, xi →ng i ui . Donc, X →ng u. 

Lemme 3 La classe AlgΣ des langages algébriques sur un alphabet Σ est close
par union, concaténation et étoile.
Preuve. Soit G1 = (Σ, N1 , R1 , S1 ) et G1 = (Σ, N1 , R1 , S1 ) deux gram-
maires algébriques. Sans perte de généralité (en renommant les non-terminaux
si nécessaire), on peut supposer N1 ∩ N2 = ∅. Soit S un nouveau non-terminal
n’appartenant pas à N1 ∪ N2 . Alors, L(G1 ) ∪ L(G2 ) = L(G) où G = (Σ, N1 ∪
N2 ∪ {S}, R1 ∪ R2 ∪ {S → S1 | S2 }, S) est algébrique; L(G1 )L(G2 ) = L(G) où
G = (Σ, N1 ∪N2 ∪{S}, R1 ∪R2 ∪{S → S1 S2 }, S) est algébrique; L(G1 )∗ = L(G)
où G = (Σ, N1 ∪ {S}, R1 ∪ {S → ε | S1 S}, S) est algébrique. 

4
3.1 Arbres de dérivation
Un arbre de dérivation est un arbre dont les noeuds sont étiquettés par un
élément de Σ ∪ N , dont la racine est étiquetée par S et tel que, si un noeud est
étiqueté par X et ses sous-arbres sont étiquetés par a1 , . . . , an respectivement,
alors X → a1 . . . an ∈ R.
A toute séquence de réécriture aboutissant à un mot u, on peut associer un
arbre de dérivation dont les feuilles, prises de gauche à droite, forment le mot
u. Par exemple, la réduction (1) a l’arbre de dérivation:

S + S

1 S * S

2 2

Inversement, à tout arbre de dérivation, on peut associer une séquence de

réécritures aboutissant au mot formé par les feuilles de l’arbre prises de gauche
à droite. Par exemple, on réécrivant à chaque étape le non-terminal le plus à
gauche possible, comme dans la réduction (1).
Dans une grammaire quelconque, le résultat d’une réduction dépend du
choix, à chaque étape, de la règle utilisée et de la position à laquelle on l’applique.
Dans une grammaire algébrique, le résultat ne dépend que du choix de la règle:
deux réductions qui ne diffèrent que par le choix des positions ont le même arbre
de dérivation. Ainsi, la réduction

S →S+S →1+S →1+S∗S →1+S∗2→1+2∗2

(le 2e argument de ∗ est réduit avant son 1er argument) a le même arbre de
dérivation que la réduction (1). Par contre,

S →S∗S →S∗2→S+S∗2→1+S∗2→1+2∗2

(on applique S → S ∗ S avant S → S + S) a un arbre de dérivation différent

même si le mot engendré est le même (1 + 2 ∗ 2):

5
 S

S * S

S + S 2

1 2

On dit qu’une grammaire G est ambiguë s’il existe un mot u ∈ L(G) ayant
deux arbres de dérivations différents. Ainsi, la grammaire de (1) est ambiguë
car 1 + 2 ∗ 2 peut être interprété soit comme 1 + (2 ∗ 2) = 5 (c’est le premier arbre
de dérivation), soit comme (1 + 2) ∗ 2 = 6 (c’est le second arbre de dérivation).
Remarque: il est indécidable de savoir si une grammaire est ambiguë ou pas.
Certains langages algébriques sont inhéremment ambiguë: il n’existe aucune
grammaire non-ambiguë les générant.

3.2 Résolution d’équations par itération

Nous allons commencer par voir un théorème très utile pour justifier la termi-
naison d’un algorithme consistant à itérer une fonction que nous utiliserons de
nombreuses fois par la suite.
Etant donné un ensemble E, soit ℘(E) l’ensemble des parties de E.
Une relation ≤ sur E est une relation d’ordre si elle est réflexive, transitive
et antisymétrique (si x ≤ y et y ≤ x, alors x = y).
Une fonction F sur E est monotone si x ≤ y implique F (x) ≤ F (y).
Un élément x est un minorant (resp. majorant) d’une partie A de E si x est
plus petit (resp. grand) que ou égal à tout élément de A.
La borne inférieure d’une partie A de E est, s’il existe, le plus grand minorant
de A: x est la borne inférieure de A si x est un minorant de A et tout minorant
de A est plus petit que ou égal à x.
Symétriquement, la borne supérieure d’une partie A de E est, s’il existe, le
plus petit majorant de A: x est la borne supérieure de A si x est un majorant
de A et tout majorant de A est plus grand que ou égal à x.
Un ensemble E muni d’une relation d’ordre ≤ est un treillis complet si toute
partie de E admet une borne inférieure et une borne supérieure.
Par exemple, pour tout ensemble N , (℘(N ), ⊆) S est un treillis: la borne
supérieure d’une famille (Ai )i∈I de parties de N est i∈I Ai , la borneTinférieure
de ∅ est N , et la borne inférieure d’une famille non vide (Ai )i∈I est i∈I Ai .
Autre exemple de treillis: étant donné un ensemble quelconque D et un
treillis (E, ≤E ), l’ensemble D → E des fonctions de D dans E avec l’ordre
f ≤ g ssi, pour tout x ∈ D, f (x) ≤E f (y).

6
 Figure 1: Treillis ℘({a, b, c})

{a, b, c}

{a, b} {a, c} {b, c}

{a} {b} {c}

Théorème 1 (Tarski) Si (E, ≤) est un treillis complet à n éléments et F une

fonction monotone sur E, alors l’équation F (Y) = Y admet une plus petite
solution A qu’on peut calculer de la façon suivante. Soit A0 le plus petit élément
de E et, pour tout i ∈ N, soit Ai+1 = F (Ai ). Alors, il existe k ≤ n tel que
A = Ak .
Preuve. Montrons que, pour tout i ∈ N, Ai ≤ Ai+1 , par récurrence sur
i. Si i = 0, nous avons Ai = A0 ≤ A1 , quelque soit A1 . Si i > 0, alors nous
avons Ai−1 ≤ Ai par hypothèse de récurrence. Donc, par monotonie, nous avons
Ai = F (Ai−1 ) ≤ F (Ai ) = Ai+1 .
Maintenant, comme E est fini, il y a un nombre fini d’inclusions strictes.
Donc, il existe k ≤ n tel que, pour tout i ≥ k, Ai = Ak . En particulier, Ak est
solution de F (Y) = Y.
Montrons maintenant que c’est la plus petite solution. Soit Y un élément
de E tel que F (Y) = Y. Montrons que, pour tout i ∈ N, Ai ≤ Y, par récur-
rence sur i. Si i = 0, alors Ai ≤ Y car A0 est le plus petit élément de E. Si
i > 0 alors, par hypothèse de récurrence, Ai−1 ≤ Y. Donc, par monotonie,
Ai = F (Ai−1 ) ≤ F (Y) = Y. 

Ainsi, si E est un treillis fini et F est monotone, alors le programme suivant

termine avec X = Y = A:

X := plus_petit_element; Y := F(X);
tant que X <> Y faire { X := Y; Y := F(X) }

7
3.3 Grammaires propres
Une grammaire algébrique G = (Σ, N , R, S) est propre si les conditions suivantes
sont vérifiées:
• elle ne contient aucune règle de la forme X → ε, sauf S → ε si ε ∈ L(G) et,
dans ce cas, S ne doit apparaître dans aucun membre droit de règle;
• elle ne contient aucune règle unaire, i.e. de la forme X → Y .

Lemme 4 Si G est une grammaire algébrique, alors il existe une grammaire

algébrique G0 ne contenant pas ε et telle que L(G0 ) = L(G) − {ε}.
Preuve. Soit G = (Σ, N , R, S) une grammaire algébrique.
Première étape: on calcule l’ensemble E des non-terminaux X effaçables,
c’est-à-dire, tel que X →∗G ε.
On remarque que E = F (E) où F est la fonction sur ℘(N ) telle que F (Y) =
{X ∈ N | ∃r ∈ Y ∗ , X → r ∈ R}. En effet, si X →∗ ε alors il existe X → r ∈ R
tel que X → r →∗ ε. Comme r →∗ ε, r = X1 . . . Xn avec Xi ∈ N . Donc,
pour tout i, Xi ∈ E et X ∈ F (E). Réciproquement, si X ∈ F (E) alors il existe
X → r ∈ R tel que r ∈ E ∗ . Donc, X →∗ ε.
On vérifie ensuite que F est monotone: si Y ⊆ Z, alors F (Y) ⊆ F (Z). En
effet, soit X ∈ F (Y). Alors, il existe r ∈ Y ∗ tel que X → r ∈ R. Comme
Y ∗ ⊆ Z ∗ , nous avons X ∈ F (Z).
Ainsi, d’après le théorème de Tarski, l’équation F (Y) = Y admet une plus
petite solution A calculable par itération de F à partir de ∅. Donc, A ⊆ E.
On prouve enfin que E ⊆ A en montrant que si X →k ε alors X ∈ A, par
récurrence sur k ≥ 1. Si k = 1, alors X → ε ∈ R et X ∈ F (∅) ⊆ A. Si k > 1,
alors X → X1 . . . Xn et, pour tout i, Xi →ni ε avec ni < n. Par hypothèse de
récurrence, Xi ∈ A. Donc, X ∈ F (A) = A.
Deuxième étape: pour chaque règle X → u ∈ R, rajouter toutes les règles
X → v où v est obtenu en remplaçant dans u un nombre quelconque de non-
terminaux effaçables par ε, et éliminer toutes les règles de la forme X → ε. On
obtient ainsi G0 = (Σ, N , R0 , S) où R0 = {X → v | X → u ∈ R, u →∗E v, v 6= ε}
où →E est la relation de réécriture engendrée par les règles {X → ε | X ∈ E}.
Montrons maintenant que L(G0 ) ⊆ L(G) − {ε}. Soit u ∈ L(G0 ). Alors
S →∗G0 u. Par définition, nous avons →G0 ⊆ →G →∗E et →E ⊆ →∗G . Donc,
S →∗G u.
Montrons enfin que L(G)−{ε} ⊆ L(G0 ). Soit u ∈ L(G)−{ε}. Alors S →∗G u
et u 6= ε. Montrons que S →∗G0 u par récurrence sur le nombre de ε-règles
utilisées, c’est-à-dire, de la forme X → ε. Si aucune ε-règle n’est utilisée, alors
S →∗G0 u car toute règle de G qui n’est pas de la forme X → ε est incluse dans
G0 . Si une ε-règle est utilisée, nous avons une étape de réécriture de la forme
aXb →G ab. Celle-ci ne peut pas être la première étape de réécriture car, sinon,
nous aurions X = S et ab = ε = u. Donc celle-ci est précédée d’une séquence
de réécritures de la forme cY d →G cαXβd →∗G aXb avec Y → αXβ ∈ R,
cα →∗G a et βd →∗G b. On peut alors remplacer la séquence cY d →∗G ab par
cY d →G0 cαβd →∗G ab qui utilise une ε-règle de moins. 

8
Lemme 5 Toute grammaire algébrique G ne contenant pas ε est effectivement
équivalente à une grammaire algébrique ne contenant pas ε et n’ayant pas de
règle unaire.
Preuve. Soit G = (Σ, N , R, S) une grammaire algébrique.
Premièrement, pour tous non-terminaux X et Y tel que X →∗ Y 6= X, et
toute règle Y → r ∈ R avec r ∈ / N , on rajoute la règle X → r. Deuxièmement,
on élimine toutes les règles unaires. On obtient ainsi G0 = (Σ, N , R0 , S) où
R0 = {X → u | X →∗ Y → u ∈ R, Y 6= X, u ∈ / N }.
Etant donné Z, comment calculer S(Z) = {X ∈ N | Z →∗ X 6= Z}?
On remarque que S(Z) = F (S(Z)) où F est la fonction sur ℘(N ) telle que
F (Y) = {X ∈ N | ∃Y ∈ Y, Y → X ∈ R, X 6= Z}. En effet, supposons que
Z →∗ X 6= Z. Comme G ne contient pas ε, il existe Y → X ∈ R tel que
Z →∗ Y → X. Si Y = Z ou Y 6= Z, on a X ∈ F (S(Z)). Réciproquement,
supposons que X ∈ F (S(Z)). Alors il existe Y ∈ S(Z) tel que Y → X ∈ R.
Donc, X ∈ S(Z).
On vérifie ensuite que F est monotone: si Y ⊆ Z, alors F (Y) ⊆ F (Z).
Ainsi, d’après le théorème de Tarski, l’équation F (Y) = Y admet une plus
petite solution A calculable par itération de F à partir de ∅. Donc, A ⊆ S(Z).
Prouvons maintenant que S(Z) ⊆ A en montrant que si Z →k X alors
X ∈ A, par récurrence sur k. Si k = 1, alors X ∈ F (∅) ⊆ A. Si k > 1 alors,
comme G ne contient pas ε, il existe Y → X ∈ R tel que Z →k−1 Y → X. Si
Y = Z alors Y ∈ F (∅) ⊆ A. Sinon, par hypothèse de récurrence, Y ∈ A. Dans
les deux cas, X ∈ F (A) = A.
Nous avons L(G0 ) ⊆ L(G) car →G0 ⊆ →+ G.
Montrons maintenant que, si S →∗G u, alors S →∗G0 u, par récurrence sur
le nombre de règles unaires utilisées. Si une règle unaire est utilisée, alors la
séquence de réécriture contient une sous-séquence de la forme aXb →G aY b →∗G
a0 Y b0 →G a0 vb0 avec v ∈
/ N . Mais cette sous-séquence peut être remplacée par
aXb →G0 avb →∗G a0 vb0 qui utilise une règle unaire de moins. 

Lemme 6 Toute grammaire algébrique est effectivement équivalente à une gram-

maire algébrique propre.

Preuve. Soit G une grammaire algébrique. Par le lemme 4, il existe une

grammaire algébrique G1 ne contenant pas ε et telle que L(G1 ) = L(G) − {ε}.
Par le lemme 5, il existe une grammaire algébrique G2 = (Σ, N2 , R2 , S2 ) ne
contenant pas ε et n’ayant pas de règle unaire telle que L(G2 ) = L(G1 ). Si
ε∈/ L(G), alors nous prenons G2 . Si par contre ε ∈ L(G) alors nous prenons
G3 = (Σ, N3 , R3 , S3 ) où S3 est un nouveau non-terminal n’appartenant pas à
N2 , N3 = N2 ∪ {S3 } et R3 = R2 ∪ {S3 → ε} ∪ {S3 → u | S2 → u ∈ R2 }. 

Exemple 1 G = {S → AA | BB, A → ε | aS, B → ε | bS}

1. On calcule les non-terminaux effaçables. A est effaçable à cause de la règle
A → ε. B est effaçable à cause de la règle B → ε. Ainsi S est aussi effaçable
à cause de la règle S → AA et du fait que A est lui-même effaçable.

9
2. On rajoute toutes les règles possibles en effaçant un ou plusieurs non-terminal
effaçables, à savoir: S → A | ε | B, A → a, B → b.
3. On efface toutes les ε-règles. On obtient ainsi: S → AA | BB | A | B, A →
aS | a, B → bS | b.
4. On calcule les successeurs de chaque non-terminal: S(S) = {A, B}, S(A) = ∅,
S(B) = ∅.
5. On rajoute toutes les règles X → u telles que X →∗ Y → u ∈
/ N et Y 6= X,
à savoir: S → aS | a | bS | b.
6. On élimine toutes les règles unaires. On obtient ainsi: S → AA | BB | aS |
a | bS | b, A → aS | a, B → bS | b.

3.4 Grammaires réduites

Un non-terminal X est improductif s’il ne génère aucun mot: LG (X) = ∅. Il
est inaccessible si aucun arbre de dérivation ne contient X. Il est inutile s’il est
improductif ou inaccessible.
Une grammaire G = (Σ, N , R, S) est réduite si R ne contient aucun non-
terminal inutile.

Lemme 7 Toute grammaire algébrique G = (Σ, N , R, S) est effectivement

équivalente à une grammaire algébrique réduite G0 = (Σ, N , R0 , S) où R0 ⊆ R.
Preuve. Nous procédons en deux étapes.
Première étape: on calcule l’ensemble P des non-terminaux productifs et
on élimine toutes les règles contenant un non-terminal improductif. On obtient
alors G1 = (Σ, N , R1 , S) où R1 = {X → u ∈ R | u ∈ (Σ ∪ P)∗ }.
Comment calculer P? On remarque que P = F (P) où F est la fonction sur
℘(N ) telle que F (Y) = {X ∈ N | ∃X → u ∈ R, u ∈ (Σ∪Y)∗ }. On vérifie ensuite
que F est monotone. Ainsi, d’après le théorème de Tarski, l’équation Y = F (Y)
admet une plus petite solution A ⊆ P calculable par itération de F à partir de
∅. Nous prouvons maintenant que P ⊆ A en montrant que, si X →k u ∈ Σ∗
alors X ∈ A, par récurrence sur k ≥ 1. Si k = 1 alors X ∈ F (∅) ⊆ A. Si
k > 1 alors il existe X → a1 . . . an ∈ R avec ai ∈ Σ ∪ N , u1 , . . . , un ∈ Σ∗ , et
k1 , . . . , kn < n tels que u = u1 . . . un et, pour tout i, ai →ki ui ∈ Σ∗ . Si ai ∈ N
alors, par hypothèse de récurrence, ai ∈ A. Donc, X ∈ F (A) = A.
Deuxième étape: à partir de G1 , on calcule l’ensemble A des non-terminaux
accessibles depuis S et on élimine toutes les règles contenant un non-terminal
inaccessible. On obtient alors G2 = (Σ, N , R2 , S) où R2 = {X → u ∈ R1 | u ∈
(Σ ∪ A)∗ }.
Comment calculer A? On remarque que A = G(A) où G(Y) = {X ∈ N |
∃u, ∃v, ∃Y ∈ Y, Y → uXv ∈ R}. On vérifie que G est monotone. Ainsi, d’après
le théorème de Tarski, l’équation G(Y) = Y admet une plus petite solution
A ⊆ A calculable par itération de G à partir de ∅. On prouve ensuite que
A ⊆ A en montrant que, si S →k uXv alors X ∈ A, par récurrence sur k ≥ 0.

10
 On vérifie maintenant que L(G) = L(G2 ). Puisque G et G2 ont le même
non-terminal de départ et R2 ⊆ R, L(G2 ) ⊆ L(G). Montrons maintenant que
L(G) ⊆ L(G2 ). Soit u ∈ L(G). Alors S →∗G u. Si X → v est une règle utilisée
dans cette dérivation, nous avons que X et tous les non-terminaux de v sont
productifs et accessibles. Donc, X → v ∈ R2 et S →∗G2 u. 

Remarque: l’ordre des étapes est important car éliminer une règle contenant
un non-terminal inaccessible X ne peut pas rendre improductif un non-terminal
Y productif et accessible (si, dans une séquence S →∗ aY b →∗ avb, on utilise une
règle X → u, alors X est accessible). Par contre, éliminer une règle contenant
un non-terminal improductif peut rendre inaccessible un non-terminal productif
et accessible. Par exemple, avec R = {S → aA | bBB | abAS | BC, A → aB |
bA | a, B → aB | bB, C → aA | bS | a}, nous avons P = {A, C} ∪ {S}
(B est improductif), R1 = {S → aA | abAS, A → bA | a, C → aA | bS | a},
A = {S}∪{A} (C est inaccessible) et donc R2 = {S → aA | abAS, A → bA | a}.
Par contre, si nous avions fait l’étape 2 avant l’étape 1, nous aurions obtenu
A = N (tous les non-terminaux sont accessibles), R1 = R, P = {A, C} ∪ {S}
(B est improductif) et R2 = {S → aA | abAS, A → bA | a, C → aA | bS | a} où
C est inaccessible.

Exemple 2 S → AC|BS|B
A → aA|aF
B → CF |b
C → cC|D
D → aD|BD|C
E → aA|BSA
F → bB|b

1. B est productif car B → b. F est productif car F → b. Donc S est productif

car S → B, et A est productif car A → aF . Donc E est productif car
E → aA. Par contre, C et D sont improductifs. En éliminant les règles
contenant l’un d’eux, on obtient:
S → BS|B
A → aA|aF
B→b
E → aA|BSA
F → bB|b
2. A partir de S, on peut avoir B. A partir de B, aucun autre non-terminal.
Donc, seuls S et B sont accessible. A, E, F sont inaccessibles. En éliminant
les règles contenant l’un d’eux, on obtient:
S → BS|B
B→b

Lemme 8 Toute grammaire algébrique est effectivement équivalente à une gram-

maire propre et réduite.

11
 Preuve. Soit G une grammaire algébrique. Par le lemme 6, G est effec-
tivement équivalente à une grammaire algébrique propre G1 . Par le lemme 7,
G1 est effectivement équivalente à une grammaire algébrique réduite G2 dont
les règles forment un sous-ensemble des règles de G1 . Donc, G2 est également
propre. 

Remarque: l’ordre est important. Il faut d’abord rendre la grammaire pro-

pre puis la réduire car, d’une part, réduire une grammaire ne fait qu’éliminer
des règles et donc préserve le fait d’être propre, et d’autre part, rendre une
grammaire propre peut rendre certains symboles inutiles. Par exemple, {S →
XY, X → ε, Y → ε} est réduite et non propre. En la rendant propre, on obtient
{S → ε | XY } où X et Y sont inutiles.
L’existence de grammaires propres et réduites va nous donner un moyen de
vérifier qu’un langage n’est pas algébrique (lemme de pompage) et que l’analyse
syntaxique est décidable pour les langages algébriques.

3.5 Lemme de pompage

Lemme 9 (Pompage) Pour tout langage algébrique L, il existe un entier N ≥
0 tel que, pour tout mot u ∈ L de longueur |u| ≥ N , il existe des mots a, b, c, d, e
tels que u = abcde, bd 6= ε, |bcd| < N et, pour tout i ≥ 0, abi cdi e ∈ L.

Preuve. Soit G une grammaire algébrique propre de L.

On procède par récurrence sur |u|.
Soit m la longueur maximale d’un membre droit de règle. C’est le nombre
maximal de sous-arbres à chaque noeud d’un arbre de dérivation.
Un arbre de hauteur i (longueur de la plus grande branche) et degré m
(nombre maximal de sous-arbres à chaque noeud) a au plus mi feuilles (récur-
rence sur i). Soit alors N = mk + 1 où k est le nombre de non-terminaux. Si
|u| ≥ N , alors u admet un arbre de dérivation de hauteur > k. Il existe donc
une branche contenant deux fois le même non-terminal A. Ainsi, nous avons
S →∗ aAe, A →+ bAd et A →∗ c. Donc, pour tout i ≥ 0, abi cdi e ∈ L.
Comme G est propre, nous avons bd 6= ε et ae 6= ε.
Si |bcd| ≥ N alors on peut conclure par hypothèse de récurrence (en prenant
A comme non-terminal de départ) car A →∗ bcd et |bcd| < |u|. 

Remarque: si L est un ensemble fini de j mots (donc algébrique), alors le

lemme est trivialement vérifié en prenant N = j + 1.
Ce lemme peut servir à montrer qu’un langage n’est pas algébrique. Par
exemple, L = {an bn cn | n ∈ N}. Comme L = L1 ∩ L2 où L1 = {an bn ck |
n ∈ N, k ∈ N} et L2 = {ak bn cn | n ∈ N, k ∈ N} sont algébriques, on peut
en déduire que l’intersection de deux langages algébriques n’est pas nécessaire-
ment algébrique. Et comme L = L1 ∩ L2 , on peut également en déduire que le
complémentaire d’un langage algébrique n’est pas nécessairement algébrique.

12
3.6 Analyse syntaxique des langages algébriques
Etant donnés une grammaire G et un mot u, l’analyse syntaxique consiste à
déterminer si u appartient au langage engendré par G ou non (u ∈ L(G)?),
c’est-à-dire, s’il existe une dérivation de S à u (S →∗ u?).
On distingue deux types d’analyse:
• l’analyse descendante consiste à trouver u à partir de S (e.g. JavaCC),

• l’analyse ascendante consiste à trouver S à partir de u en prenant les règles

à l’envers (e.g. yacc, CUP).
Ce problème est décidable pour les grammaires algébriques ainsi:
1. Soit n = |u|. Si n = 0, alors vérifier si S est effaçable.

2. Sinon, calculer à partir de G une grammaire propre et réduite G0 pour L(G)−

{ε}. Il suffit alors de retourner u ∈? L b n où Lb n est l’ensemble des mots
b 0 = {S} et L
dérivables en au plus n étapes en prenant L b k ∪ {v | ∃u ∈
b k+1 = L
Lk , u → v}. En effet, comme aucun membre droit de règle n’est un non-
b
terminal ou ε, chaque étape de réécriture accroît la taille du mot engendré
d’au moins une lettre.

La complexité dans le pire cas de cet algorithme est en O(nr ) où n est la taille
du mot u et r est le nombre de règles.
Il existe de bien meilleurs algorithmes de complexité en O(n3 ) dans le pire
cas: l’algorithme de Cocke-Younger-Kasami ou l’algorithme d’Earley.

13