Université BADJI MOKHTAR ANNABA

Faculté des sciences de l’ingénieur

Département d’informatique

Théorie des langages

Support de cours
Préparé par : Dr. T. BENOUHIBA

Dernière mise à jour

Décembre 2013
 Table des matières

Table des figures iv

Liste des tableaux v

1 Notions fondamentales en théorie des langages 1

1.1 Rappels sur la théorie des ensembles . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.1 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.2 Opérations sur les ensembles . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Théorie des langages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.1 Notions sur les mots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.2 Longueur d’un mot . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.3 Concaténation des mots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.4 Notions sur les langage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Grammaire (système générateur de langage) . . . . . . . . . . . . . . . . . . . . . 4
1.3.1 Exemple introductif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3.2 Classification de Chomsky . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4 Les automates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.4.1 Configuration d’un automate . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.4.2 Classification des automates . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.5 Exercices de TD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2 Les automates à états finis (AEF) 11

2.1 Généralités sur les AEF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.1.1 Représentation par table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.1.2 Représentation graphique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2 Les automates et le déterminisme . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.1 Notion de déterminisme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.2 Déterminisation d’un automate à états fini . . . . . . . . . . . . . . . . . . 14
2.2.3 Déterminisation d’un AEF sans ε-transition . . . . . . . . . . . . . . . . . 14

i
 ii

2.2.4 Déterminisation avec les ε-transitions . . . . . . . . . . . . . . . . . . . . . 15

2.3 Minimisation d’un AEF déterministe . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.3.1 Les états inaccessibles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.3.2 Les états β-équivalents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.3.3 Minimiser un AEF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.4 Opérations sur les automates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.4.1 Le complément . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.4.2 L’opération d’entrelacement . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.4.3 Produit d’automates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.4.4 Le langage miroir . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.5 Exercices de TD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

3 Les langages réguliers 27

3.1 Les expressions régulières E.R . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.1.1 Expressions régulières ambiguës . . . . . . . . . . . . . . . . . . . . . . . . 28
3.1.2 Comment lever l’ambiguïté d’une E.R ? . . . . . . . . . . . . . . . . . . . . 28
3.2 Les langages réguliers, les grammaires et les automates à états finis . . . . . . . 28
3.2.1 Passage de l’automate vers l’expression régulière . . . . . . . . . . . . . . 29
3.2.2 Passage de l’expression régulière vers l’automate . . . . . . . . . . . . . . 29
3.2.3 Passage de l’automate vers la grammaire . . . . . . . . . . . . . . . . . . . 32
3.2.4 Passage de la grammaire vers l’automate . . . . . . . . . . . . . . . . . . . 33
3.3 Propriétés des langages réguliers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.3.1 Stabilité par rapport aux opérations sur les langages . . . . . . . . . . . . 33
3.3.2 Lemme de la pompe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.4 Exercices de TD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

4 Les langages algébriques 38

4.1 Les automates à piles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.1.1 Les automates à piles et le déterminisme . . . . . . . . . . . . . . . . . . . 39
4.2 Les grammaires hors-contextes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.2.1 Arbre de dérivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.2.2 Notion d’ambiguïté . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.2.3 Équivalence des grammaires hors-contextes et les automates à piles . . . 43
4.3 Simplification des grammaires hors-contextes . . . . . . . . . . . . . . . . . . . . 43
4.3.1 Les grammaires propres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.4 Les formes normales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.4.1 La forme normale de Chomsky . . . . . . . . . . . . . . . . . . . . . . . . . 44
 iii

4.4.2 La forme normale de Greibach . . . . . . . . . . . . . . . . . . . . . . . . . 45

 Table des figures

2.1 L’automate de am bn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2 L’automate des mots contenant le facteur ab . . . . . . . . . . . . . . . . . . . . . 13
2.3 L’automate reconnaissant les mots contenant le facteur ab (en ayant des ε-
transitions) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.4 L’automate déterministe qui reconnaît les mots ayant le facteur ab . . . . . . . . 15
2.5 Exemple d’états β-équivalents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.6 Comment obtenir l’automate du langage complémentaire (d’un automate com-
plet) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.7 Si l’automate n’est pas complet, on ne peut pas obtenir l’automate du langage
inverse. L’automate obtenu reconnaît les mots contenant au plus 1 a. . . . . . . . 20
2.8 Si l’automate n’est pas déterministe, on ne peut pas trouver l’automate du lan-
gage complémentaire. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.9 Exemple d’entrelacement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.10 Exemple d’intersection de produit d’automates . . . . . . . . . . . . . . . . . . . 22

4.1 Exemple d’un arbre de dérivation . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

4.2 Un premier arbre de dérivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.3 Deuxième arbre de dérivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

iv
 Liste des tableaux

2.1 Table de transition de l’automate de la figure 2.2 . . . . . . . . . . . . . . . . . . . 13

v
 Chapitre 1

Notions fondamentales en théorie des

langages

1.1 Rappels sur la théorie des ensembles

1.1.1 Définitions

Définition 1 : Un ensemble est une collection d’objets sans répétition.

Exemple 1 : {a, b, c, d, ..., z} : l’ensemble des lettres minuscules.

Si un objet appartient à un ensemble A, on dit qu’il est élément de A et l’on note x ∈ A.

On a donc les propriétés suivantes :
– Si ∀x ∈ A, x ∈ B alors on dit que A est inclus dans B et l’on note A ⊆ B ;
– A = B si A ⊆ B et B ⊆ A (on dit que A est un sous-ensemble de B) ;
– Par conséquent, ∅ ⊆ A, A étant un ensemble quelconque.

1.1.2 Opérations sur les ensembles

Soient A et B deux sous-ensembles quelconques de Ω, on définit alors les opérations
suivantes :
– Union : notée A ∪ B qui comporte tout élément appartenant à A ou B ;
– Intersection : notée A ∩ B qui comporte tout élément appartenant à A et B ;
– Différence : notée A − B qui comporte tout élément appartenant à A et qui n’appartient
pas à B ;
– Complément : notée A = Ω − A
– Cardinalité : notée card(A) qui est le nombre d’éléments de A ;
– Produit cartésien : noté A × B qui est l’ensemble des paires (a, b) telles que a ∈ A et
b ∈ B. Il est clair que card(A × B) = card(A).card(B) ;
– L’ensemble des parties de A : notée 2A qui est l’ensemble de tous les sous-ensembles de
A. On a : card(2A ) = 2card(A) .

Exemple 2 : A = {a, b}, B = {a, c}, Ω = {a, b, c} :

– A ∩ B = {a} ;
– A ∪ B = {a, b, c} ;

1
1.2. Théorie des langages 2

– A − B = {b} ;
– A = {c} ;
– A × B = {(a, a), (a, b), (b, a), (b, c)} ;
– 2A = {∅, {a}, {b}, {a, b}}

1.2 Théorie des langages

1.2.1 Notions sur les mots

Définition 2 : Un symbole est une entité abstraite. Les lettres et les chiffres sont des exemples
de symboles utilisés fréquemment, mais des symboles graphiques peuvent également être
employés.

Définition 3 : Un alphabet est un ensemble de symboles. Il est également appelé le vocabu-

laire.

Définition 4 : Un mot (ou bien une chaîne) défini sur un alphabet A est une suite finie de
symboles juxtaposés de A.

Exemple 3 :
– Le mot 1011 est défini sur l’alphabet {0, 1}
– Le mot 1.23 est défini sur l’alphabet {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, .} ;

1.2.2 Longueur d’un mot

Si w est un mot, alors sa longueur est définie comme étant le nombre de symboles contenus
dans w, elle est noté par |w|. Par exemple, |abc| = 3, |aabba| = 5. En particulier, on note le
mot dont la longueur est nulle par ε : |ε| = 0.
On définit également la cardinalité d’un mot w par rapport à un symbole a ∈ A : |w|a
comme étant le nombre d’occurrence de a dans w. Par exemple, |abc|a = 1, |aabba|b = 2.

1.2.3 Concaténation des mots

Soient w1 et w2 deux mots définis sur l’alphabet A. La concaténation de w1 et w2 est un
mot w défini sur le même alphabet. w est obtenu en écrivant w1 suivi de w2 , en d’autres
termes, on colle le mot w2 à la fin du mot w1 :

w1 = a1 ...an , w2 = b1 b2 ...bm
w = a1 ...an b1 b2 ...bm

La concaténation est noté par le point, mais il peut être omis. On écrira alors : w = w1 .w2 =
w1 w2 .
1.2. Théorie des langages 3

Propriété de la concaténation
Soient w, w1 et w2 trois mots définis sur l’alphabet A :
– |w1 .w2 | = |w1 | + |w2 | ;
– ∀a ∈ A : |w1 .w2 |a = |w1 |a + |w2 |a ;
– (w1 .w2 ).w3 = w1 .(w2 .w3 ) (la concaténation est associative)
– w.ε = ε.w = w ;

L’exposant
L’opération w.w est notée par w2 . En généralisant, on note wn = w...w
| {z } . En particulier,
n fois
l’exposant 0 fait tomber sur ε : w0 = ε (le mot w est répété 0 fois).

Le mot miroir
Soit w = a1 a2 ...an un mot sur A (ai ∈ A). On appelle mot miroir de w et on le note par
wR le mot obtenu en écrivant w l’envers, c’est-à-dire que wR = an ...a2 a1 . Il est donc facile de
voir que (wR )R = w.
Certains mots, appelés palindromes, sont égaux à leur miroir. En d’autres termes, on lit la
même chose dans les deux directions. Par ailleurs, on peut facilement vérifier que : (u.v)R =
vR .uR .

Préfixe et suffixe
Soit w un mot défini sur un alphabet A. Un mot x (resp. y) formé sur A est un préfixe
(resp. suffixe) de w s’il existe un mot u formé sur A (resp. v formé sur A) tel que w = xu (resp.
w = vy). Si w = a1 a2 ...an alors tous les mots de l’ensemble {ε, a1 , a1 a2 , a1 a2 a3 , ..., a1 a2 ...an }
sont des préfixes de w. De même, tous les mots de l’ensemble {ε, an , an−1 an , an−2 an−1 an , ...,
a1 a2 ...an } sont des suffixes de w.

Entrelacement (mélange)
Soit u et v deux mots tel que u = u1 u2 ...un et v = v1 v2 ...vm . On appelle entrelacement de u


et v (on le note par u v) l’ensemble des mots w qui mélangent les symboles de u de v tout en


gardant l’ordre des symboles de u et de v. Par exemple, ab ac = {abac, aabc, aacb, acab}.
Cette opération est commutative.
En particulier, lorsque v se réduit un seul symbole, l’opération d’entrelacement se résume
à l’insertion dudit symbole quelque part dans le mot u. Si a est un symbole, alors u v =



{u1 .a.u2 |u1 .u2 = u}. Par exemple, ab c = {cab, acb, abc}.

1.2.4 Notions sur les langage

Définition 5 : Un langage est un ensemble (fini ou infini) de mots définis sur un alphabet
donné. Le langage qui ne contient que ε est dit langage vide.

Exemple 4 :
– Langage des nombre binaires définies sur l’alphabet {0, 1} (infini) ;
1.3. Grammaire (système générateur de langage) 4

– Langage des mots de longueur 2 défini sur l’alphabet {a, b}={aa, ab, ba, bb} ;
– Langage Pascal (quel est le vocabulaire ?) ;
– Langue française (quel est le vocabulaire ?).

Opérations sur les langages

Soit L, L1 et L2 trois langages définis sur l’alphabet X, on définit les opérations suivantes :
– Union : notée par + ou | plutôt que ∪. L1 + L2 = {w|w ∈ L1 ∨ w ∈ L2 } ;
– Intersection : L1 ∩ L2 = {w|w ∈ L1 ∧ w ∈ L2 } ;
– Concaténation : L1 .L2 = {w|∃u ∈ L1 , ∃v ∈ L2 : w = uv} ;
– Exposant : Ln = L.L...L
| {z } = {w|∃u1 , u2 , ...un ∈ L : w = u1 u2 ...un } ;
n fois S
– Fermeture transitive de Kleene : notée L∗ = i>0 Li . En particulier, si L = X on obtient
X∗ c’est-à-dire l’ensemble de tous les mots possibles sur l’alphabet X. On peut ainsi
définir un langage comme étant S un sous-ensemble quelconque de X∗ ;
– Fermeture non transitive : L = i>0 Li ;
+

– Le langage miroir : LR = {w|∃u ∈ L : w = uR } ;

– Le mélange de langages : L L ′ = {u v|u ∈ L, v ∈ L ′ }. En particulier, lorsque le langage


L ′ se réduit à un seul mot composé à d’un seul symbole a, on a : L a = {u.a.v|(u.v) ∈ L}

Propriétés des opérations sur les langages

Soit L, L1 , L2 , L3 quatre langage définis sur l’alphabet A :
– L∗ = L+ + {ε} ;
– L1 .(L2 .L3 ) = (L1 .L2 ).L3 ;
– L1 .(L2 + L3 ) = (L1 .L2 ) + (L1 .L3 ) ;
– L.L 6= L ;
– L1 .(L2 ∩ L3 ) 6= (L1 ∩ L2 ).(L1 ∩ L3 ) ;
– L1 .L2 6= L2 .L1 .
– (L∗ )∗ = L∗ ;
– L∗ .L∗ = L∗ ;
– L1 .(L2 .L1 )∗ = (L1 .L2 )∗ .L1 ;
– (L1 + L2 )∗ = (L∗1 L∗2 )∗ ;
– L∗1 + L∗2 6= (L1 + L2 )∗

1.3 Grammaire (système générateur de langage)

L’une des notions les plus utilisées en théorie des langages est la notion de grammaire.
Pour bien l’illustrer, nous allons prendre un exemple.

1.3.1 Exemple introductif

Pour analyser une classe de phrases simples en français, on peut supposer qu’une phrase
est composée de la manière suivante :

– PHRASE → ARTICLE SUJET VERBE COMPLEMENT

1.3. Grammaire (système générateur de langage) 5

– SUJET → "garçon" ou "fille"

– VERBE → "voit" ou "mange" ou "porte"

– COMPLEMENT → ARTICLE NOM ADJECTIF

– ARTICLE → "un" ou "le"

– NOM → "livre" ou "plat" ou "wagon"

– ADJECTIF → "bleu" ou "rouge" ou "vert"

En faisant des substitutions (on remplace les parties gauches par les parties droites) on
arrive à générer les deux phrases suivantes.

Le garçon voit un livre rouge

Une fille mange le plat vert

De même, à partir des phrases, on peut retrouver la catégorie de chaque mot en utilisant ces
règles. On dit ici que PHRASE, ARTICLE, SUJET sont des concepts du langage ou encore des
symboles non-terminaux (car ils ne figurent pas dans la phrase aux quelles on s’intéresse). Les
symboles GARCON, FILLE, VOIT, MANGE, etc sont des terminaux puisqu’ils figurent dans
le langage final (les phrases).
Le processus de génération de la phrase à partir de ces règles est appelé dérivation.

Définition 6 : On appelle grammaire le quadruplet (V, N, X, R)

– V est un ensemble fini de symboles dits terminaux, on l’appelle également vocabulaire
terminal ;
– N est un ensemble fini (disjoint de V) de symboles dits non-terminaux ou encore concepts ;
– S un non-terminal particulier appelé axiome (point de départ de la dérivation) ;
– R est un ensemble de règles de productions de la forme g → d tel que g ∈ (V + N)+ et
d ∈ (V + N)∗ .

Les règles de la forme ε → α sont interdites. Pourquoi ?

Par convention, on utilisera les lettres majuscules pour les non-terminaux, et les lettres
minuscules pour représenter les terminaux.
∗
Soit une suite de dérivations : w1 → w2 → w3 → ... → wn alors on écrira : w1 −→ wn . On
dit alors qu’il y a une séquence de dérivation qui mène de w1 vers wn .

Exemple 5 : Soit la grammaire G = ({a}, {S}, S, {S → aS|ε}) génère le langage {ε, a, aa, aaa} =
a∗ selon l’arbre suivant :

ε aS

a aaS

aa aaaS
1.3. Grammaire (système générateur de langage) 6

Définition 7 : Soit une grammaire G = (V, N, S, R). On dit que le mot u appartenant à V ∗ est
dérivé (ou bien généré) à partir de G s’il existe une suite de dérivation qui, partant de l’axiome
∗
S, permet d’obtenir u : S −→ u. Le langage de tous les mots générés par la grammaire G est
noté L(G).

Définition 8 : Etant donnée une grammaire G = (V, N, S, R), les arbres de syntaxe de G sont
des arbres où les noeuds internes sont étiquetés par des symboles de N, et les feuilles étiquetés
par des symboles de V, tels que, si le nœud p apparaît dans l’arbre et si la règle p → a1 ...an
(ai terminal ou non terminal) est utilisée dans la dérivation, alors le nœud p possède n fils
correspondant aux symboles ai .

Si l’arbre syntaxique a comme racine S, alors il est dit arbre de dérivation du mot u tel que
u est le mot obtenu en prenant les feuilles de l’arbre dans le sens gauche→droite et bas→haut.

1.3.2 Classification de Chomsky

La classe d’une grammaire est reconnue grâce à la forme de ses règles de production.
Chomsky a établi une classification hiérarchique qui permet de classer les grammaires en
quatre catégories. A chacune des catégories, on associe un type d’automate minimal permet-
tant de reconnaître les langages générés par ces grammaires. Une grammaire de type i génère
un langage de type j tel que j > i.

Soit G = (V, N, S, R) une grammaire, les classes de grammaires de Chomsky sont :

– Type 3 ou grammaire régulière (à droite) : toutes les règles de production sont de la
forme g → d où g ∈ N et d = aB tel que a appartient à V ∗ et B appartient à N ∪ {ε} ;
– Type 2 ou grammaire hors-contexte : toutes les règles de production sont de la forme
g → d où g ∈ N et d ∈ (V + N)∗ ;
– Type 1 ou grammaire contextuelle : toutes les règles sont de la forme g → d tel que
g ∈ (N + V)+ , d ∈ (V + N)∗ et |g| 6 |d|. De plus, si ε apparaît à droite alors la partie
gauche doit seulement contenir S (l’axiome). On peut aussi trouver la définition suivante
des grammaires de type 1 : toutes les règles sont de la forme αBβ → αωβ tel que
α, β ∈ (V + N)∗ , B ∈ X et ω ∈ (V + N)∗ ;
– Type 0 : aucune restriction. Toutes les règles sont de la forme : d → g, g ∈ (V + N)+ ,
d ∈ (V + N)∗
Il existe une relation d’inclusion entre les types de grammaires selon la figure suivante :

Type3

Type2

Type1

Type0
1.4. Les automates 7

Bande en entrée

Tête de L/E

Organe
de
commande

Mémoire
auxiliaire

Le type retenu pour une grammaire est le plus petit qui satisfait les conditions.

1.4 Les automates

Les grammaires représentent un moyen qui permet de décrire un langage d’une manière
que l’on peut qualifier d’inductive. Elles montrent comment les mots du langage sont dérivés.
Pour un langage donné L, on se propose de répondre à la question w ∈ L. On peut
répondre à cette question de plusieurs façons. D’abord, on peut vérifier l’existence de w dans
la liste des mots de L (impossible à réaliser si le langage est infini). On peut également chercher
une grammaire générant L puis vérifier si cette grammaire génère L. Il existe en réalité un
troisième moyen permettant de répondre à cette question : les automates. Un automate est une
machine qui, après avoir exécuté un certain nombre d’opérations sur le mot, peut répondre à
cette question par oui ou non.

Définition 9 : Un automate est une machine abstraite qui permet de lire un mot et de ré-
pondre à la question : "un mot w appartient-il à un langage ?" par oui ou non. Aucune garantie
n’est cependant apportée concernant le temps de reconnaissance ou même la possibilité de le
faire. Un automate est composé de :

– Une bande en entrée finie ou infinie sur laquelle sera inscrit le mot à lire ;
– Un organe de commande qui permet de gérer un ensemble fini de pas d’exécution ;
– Eventuellement, une mémoire auxiliaire de stockage.

Formellement, un automate contient au minimum :

– Un alphabet pour les mots en en entrée noté X ;
– Un ensemble non vide d’états noté Q ;
– Un état initial noté q0 ∈ Q ;
– Un ensemble non vide d’états finaux qf ∈ Q ;
– Une fonction de transition (permettant de changer d’état) notée δ.

1.4.1 Configuration d’un automate

Le fonctionnement d’un automate sur un mot se fait à travers un ensemble de configura-
tions.
1.4. Les automates 8

Définition 10 : On appelle configuration d’un automate en fonctionnement les valeurs de

ses différents composants, à savoir la position de la tête L/E, l’état de l’automate et éventuel-
lement le contenu de la mémoire auxiliaire (lorsqu’elle existe). Il existe deux configurations
spéciales appelées configuration initiale et configuration finale.

Définition 11 : La configuration initiale est celle qui correspond à l’état initial q0 et où la tête
de L/E est positionnée sur le premier symbole du mot à lire.

Définition 12 : Une configuration finale est celle qui correspond à un des états finaux qf et
où le mot a été entièrement lu.

On dit qu’un mot est reconnu par un automate si, à partir d’une configuration initiale, on
arrive à une configuration finale à travers une succession de configurations intermédiaires .
On dit aussi qu’un langage est reconnu par un automate lorsque tous les mots de ce langage
sont reconnus par l’automate.

1.4.2 Classification des automates

Comme les grammaires, les automates peuvent être classés en 4 classes selon la hiérarchie
de Chomsky :
– Type 3 ou automate à états fini (AEF) : il reconnaît les langages de type 3. Sa structure
est la suivante :
– bande en entrée finie ;
– sens de lecture de gauche à droite ;
– Pas d’écriture sur la bande et pas de mémoire auxiliaire.
– Type 2 ou automate à pile : il reconnaît les langages de type 2. Sa structure est similaire
à l’AEF mais dispose en plus d’une mémoire organisée sous forme d’une pile infinie ;
– Type 1 ou automate à bornes linéaires (ABL) : il reconnaît les langages de type 1. Sa
structure est la suivante :
– Bande en entrée finie accessible en lecture/écriture ;
– Lecture dans les deux sens ;
– Pas de mémoire auxiliaire.
– Type 0 ou machine de Turing : il reconnaît les langages de type 0. Sa structure est la
même que l’ABL mais la bande en entrée est infinie.
Le tableau suivant résume les différentes classes de grammaires, les langages générés et
les types d’automates qui les reconnaissent :

Grammaire Langage Automate

Type 0 Récursivement énumérable Machine de Turing
Type 1 ou contextuelle Contextuel Machine de Turing à borne linéaire
Type 2 ou hors-contexte Algébrique Automate à pile
Type 3 ou régulière Régulier ou rationnel Automate à états fini
1.5. Exercices de TD 9

1.5 Exercices de TD

Exercice 1 : Déterminer l’alphabet pour chacun des langages suivants :

– Les nombres binaires ;
– Les nombres entiers éventuellement munis d’un signe ;
– Les nombres réels en C ;
– Les identificateurs en C ;
– Le langage C ;

Exercice 2 : Trouver les langages correspondants aux définitions suivantes :

– Tous les mots sur {a, b, c} de longueur 2 ne contenant pas un c ;
– Tous les mots sur {a, b} contenant au maximum deux a ou bien un b ;
– Tous les mots sur {a, b} qui contenant plus de a que de b ;
– Le langage L défini comme suit : ε ∈ L, si u ∈ L alors auab ∈ L

Exercice 3 :



– Calculez ε a, abca d, abca a, an b.




– Calculez {an |n > 0} a, {an bn |n > 0} a.

Exercice 4 : On note par Pref(L) l’ensemble suivant : {u|∃w ∈ L : u est préfixe de w}. Calculer
Pref(L) dans chacun des cas suivants : L = {ab, abc, ε}, L = {an bm |n, m > 0}, L = {an bn |n >
0}.
On note par Suf(L) l’ensemble suivant : {u|∃w ∈ L : u est suffixe de w}. Calculer Suf(L)
pour les langages précédents.

Exercice 5 : Définir la fermeture de Kleene (L∗ ) pour chacun des langages suivants :
– L = {ε} ;
– L = {a} ;
– L = {a, ab} ;
– L = {aa, ab, ba, bb} ;

Exercice 6 : Soit X un alphabet, trouver les mots w ∈ X∗ qui vérifient :

– w2 = w3 ;
– ∃v ∈ X∗ : w3 = v2 ;

Exercice 7 : Préciser le type de chacune des grammaires suivantes ainsi que les types des
langages qui en dérivent :
– G = ({a, b}, {S, T }, S, {S → aabS|aT , T → bS|ε}) ;
– G = ({a, b, c}, {S, T , U}, S, {S → bST a|aT b, T → abS|cU, U → S|ε}) ;
– G = ({x, +, ∗}, {S}, S, {S → S + S|S ∗ S|x}) ;
– G = ({0, 1, 2}, {S, T , C, Z, U}, S, {S → T Z, T → 0U1, T → 01, U → 0U1C|01C, C1 → 1C, CZ →
Z2, 1Z → 12})
– G = ({0, 1, 2}, {S, C, Z, T }, S, {S → T Z, T → 0T 1C|ε, C1 → 1C, CZ → Z2, 1Z → 1}) ;
1.5. Exercices de TD 10

– G = ({a, b, c}, {S, T }, S, {S → T a|Sa, T → T b|Sb|ε})

Exercice 8 : Donner, sans démonstration, les langages générés par les grammaires suivantes.
Dites, à chaque fois, de quel type s’agit-il ? :
– G = ({a}, {S}, S, {S → aS|ε}) ;
– G = ({a}, {S}, S, {S → aSa|ε}) ;
– G = ({a, b}, {S}, S, {S → aSa|bSb|ε}) ;

Exercice 9 : Donner les grammaires qui génèrent les langages suivants :

– Les nombres binaires ;
– Les mots sur {a, b} qui contiennent le facteur a

Exercice 10 : Soit G et G ′ deux grammaires qui génèrent respectivement les langages L et L ′ .

Donner une construction qui permet de trouver la grammaire de :
– L.L ′ ;
– L + L′ ;
– L∗ ;
 Chapitre 2

Les automates à états finis (AEF)

Les AEF sont les plus simples des machines de reconnaissance de langages car ils ne com-
portent pas de mémoire. Par conséquent, les langages reconnus par ce type d’automates sont
les plus simples des quatre classes de Chomsky, à savoir les langages réguliers (type 3). Par
ailleurs, les automates à états finis peuvent être utilisés pour modéliser plusieurs problèmes
dont la solution n’est pas très évidente. La série de TD propose quelques exercices dans ce
sens.

2.1 Généralités sur les AEF

Définition 13 : Un automate à états finis est machine abstraite définie par le quintuplet
(X, Q, q0 , F, δ) tel que :
– X est l’ensemble des symboles formant les mots en entrée (l’alphabet du mot à recon-
naître) ;
– Q est l’ensemble des états possibles ;
– q0 est l’état initial ;
– F est l’ensemble des états finaux (F 6= ∅, F ⊆ Q). F représente l’ensemble des états d’ac-
ceptation ;
– δ est une fonction de transition qui permet de passer d’un état à un autre selon l’entrée
en cours :
δ : Q × (X ∪ {ε}) 7→ Q
δ(qi , a) = qj ou ∅ (∅ signifie que la configuration n’est pas prise en charge)

Un mot est accepté par un AEF si, après avoir lu tout le mot, l’automate se trouve dans un
état final (qf ∈ F). En d’autres termes, un mot est rejeté par un AEF dans deux cas :
– L’automate est dans l’état qi , l’entrée courante étant a et la transition δ(qi , a) n’existe
pas (on dit que l’automate est bloqué) :
– L’automate arrive à lire tout le mot mais l’état de sortie n’est pas un état final.
Un AEF A est donc un séparateur (ou classifieur) des mots de X∗ en deux parties : l’ensemble
des mots reconnus par l’automate (notons le par L(A)) et le reste des mots (X∗ − L(A)).
Un AEF peut être représenté de deux manières : soit par une table définissant la fonction
de transition soit par graphe orienté.

11
2.2. Les automates et le déterminisme 12

2.1.1 Représentation par table

La table possède autant de lignes qu’il y d’états dans l’automate de telle sorte que chaque
ligne correspond à un état. Les colonnes correspondent aux différents symboles de l’alphabet.
Si l’automate est dans l’état i et que le symbole j est le prochain à lire, alors l’entrée (i, j) de
la table donne l’état auquel l’automate passera après avoir lu j.

Exemple 6 : L’automate qui reconnaît les mots de la forme an bm (n, m > 0) est le suivant :
({a, b}, {0, 1}, 0, {0, 1}, δ) tel que δ est donnée par la table :

État a b
0 0 1
1 - 1

2.1.2 Représentation graphique

La représentation graphique consiste à représenter l’automate par un graphe orienté.
Chaque état de l’automate est schématisé par un rond (ou sommet). Si la transition δ(qi , a) =
qj est définie, alors on raccorde le sommet qi au sommet qj par un arc décoré par le symbole
a. L’état initial est désigné par une flèche entrante au sommet correspondant tandis que les
états finaux sont marqués un double rond. Le schéma suivant reprend l’automate précédent :

a b

b
0 1

Figure 2.1 – L’automate de am bn

Lorsqu’il y a plusieurs symboles a1 , ...ak tels que (qi , al ) = qj (l = 1..k) alors on se permet
de décorer l’arc (qi , qj ) par l’ensemble a1 , ..., ak .

2.2 Les automates et le déterminisme

2.2.1 Notion de déterminisme
Un programme informatique doit, en général, être déterministe : c’est-à-dire que l’on doit
toujours connaître son comportement dans les différentes situations possibles. Par exemple,
on ne peut pas accepter un programme qui agit de deux manières différentes au même événe-
ment. Un AEF, étant une forme spéciale d’un programme informatique, doit agir de la sorte.
En d’autres mots, étant donné un mot à reconnaître, on doit connaître en avance la liste des
états par lesquels passera l’automate. Ceci revient à dire que si l’automate est dans l’état qi et
que l’entrée courante est a alors il existe au plus un état qj tel que δ(qi , a) = qj . Le cas échéant,
2.2. Les automates et le déterminisme 13

État a b
0 0,1 0
1 - 2
2 2 2

Table 2.1 – Table de transition de l’automate de la figure 2.2

on dit que l’automate est déterministe parce qu’il sait à quel état passer à tout moment. Dans
le cas inverse, l’automate doit choisir une action et la tester à terme, si la reconnaissance n’est
pas possible l’automate doit tester les autres éventualités.
En pratique, il est souvent plus facile de concevoir des automates dépourvus de cette
propriété. Heureusement, cela ne nuit en rien au fonctionnement des automates. En effet, on
verra plus tard un théorème énonçant que tout automate non déterministe peut être transformé
en un automate déterministe.
Le non déterminisme peut également provenir des transitions (arcs). En effet, rien n’inter-
dit dans la définition des AEF d’avoir des ε-transitions, c’est-à-dire des transitions décorées
avec ε. L’existence d’une ε-transition entre les états qi et qj signifie que l’on n’a pas besoin
de lire un symbole 1 pour passer de qi vers qj (attention ! l’inverse n’est pas possible). Voyons
maintenant une définition formelle de la notion du déterminisme pour les AEF.

Définition 14 : Un AEF (X, Q, q0 , F, δ) est dit déterministe si les deux conditions sont véri-
fiées :
– ∀qi ∈ Q, ∀a ∈ X, il existe au plus un état qj tel que δ(qi , a) = qj ;
– L’automate ne comporte pas de ε-transitions.

Exemple 7 : Soit le langage des mots définis sur {a, b} possédant le facteur ab. La construction
d’un AEF non déterministe est facile. La table 2.1 donne la fonction de transition (l’état initial
est l’état 0 et l’état 2 est final). La figure 2.2 reprend le même automate :

a,b a,b

a b
0 1 2

Figure 2.2 – L’automate des mots contenant le facteur ab

Exemple 8 : L’automate donné par la figure 2.3 reconnaît le même langage que le précédent
mais en utilisant des ε-transitions.

1. Par abus de langage, on dit qu’on lit ε

2.2. Les automates et le déterminisme 14

ε 1 a ε 6 a
a b ε
0
ε 3 4 5 8
ε b
ε 2 b 7

ε ε

Figure 2.3 – L’automate reconnaissant les mots contenant le facteur ab (en ayant des ε-transitions)

2.2.2 Déterminisation d’un automate à états fini

Dans la section précédente, nous avons présenté la notion de déterminisme pour un au-
tomate 2 . Il est en général plus facile de concevoir des automates non déterministes surtout
lorsque l’on utilise les expressions régulières pour dénoter les langages réguliers. Nous allons
maintenant énoncer un théorème qui nous sera d’une grande utilité lorsqu’on travaille avec
des AEF non déterministes (la démonstration de ce théorème sort du cadre de ce cours).

Théorème 1 : (appelé encore théorème de Rabin et Scott) Tout langage accepté par un AEF
non déterministe est également accepté par un AEF déterministe.

Une conséquence très importante de ce théorème peut déjà être citée (en réalité, elle dé-
coule plutôt de la démonstration de ce théorème) :

Proposition 1 : Tout AEF non déterministe peut être transformé en un AEF déterministe.

Ce résultat établit que si l’on veut construire l’automate à états fini déterministe qui re-
connaît les mots d’un certain langage, alors on peut commencer par trouver un AEF non
déterministe (ce qui est plus facile). Il suffit de le transformer, après, pour obtenir un auto-
mate à états finis déterministe.

2.2.3 Déterminisation d’un AEF sans ε-transition

En réalité, l’algorithme de déterminisation d’un AEF est général, c’est-à-dire qu’il fonc-
tionne dans tous les cas (qu’il y ait des ε-transitions ou non). Cependant, il est plus facile de
considérer cet algorithme sans les ε-transitions. Dans cette section, on suppose que l’on a un
AEF A ne comportant aucune ε-transition.

Algorithme : Déterminiser un AEF sans les ε-transitions

Principe : considérer des ensembles d’états plutôt que des états (dans l’algorithme suivant,
chaque ensemble d’états représente un état futur automate).

2. Notons que cette notion n’est pas limitées aux seuls AEF
2.2. Les automates et le déterminisme 15

1- Partir de l’état initial E(0) = {q0 } (c’est l’état initial du nouvel automate) ;
2- Construire E(1) l’ensemble des états obtenus à partir de E(0) par la transition a :
S
E(1) = q ′ ∈E(0) δ(q ′ , a)
3- Recommencer l’étape 2 pour toutes les transitions possibles et pour chaque
nouvel ensemble E(i) ;
S
E(i) = q ′ ∈E(i−1) δ(q ′ , a)
4- Tous les ensembles contenant au moins un état final du premier automate
deviennent finaux ;
5- Renuméroter les états en tant qu’états simples.

Pour illustrer cet algorithme, nous allons l’appliquer à l’automate donné par la figure 2.2.
La table suivante illustre les étapes d’application de l’algorithme (les états en gras sont des
états finaux) :

État a b État a b
0 0,1 0 0 1 0
0,1 0,1 0,2 =⇒ 1 1 2
0,2 0,1,2 0,2 2 3 2
0,1,2 0,1,2 0.2 3 3 2

La figure 2.4 donne l’algorithme obtenu (remarquons qu’il n’est pas optimal). Cet automate
n’est pas évident à trouver mais grâce à l’algorithme de déterminisation, on peut le construire
automatiquement.

b a b a

a b a
0 1 2 3

Figure 2.4 – L’automate déterministe qui reconnaît les mots ayant le facteur ab

2.2.4 Déterminisation avec les ε-transitions

Déterminiser un AEF contenant au moins une ε-transition est un peu plus compliqué
puisqu’elle fait appel à la notion de l’ε-fermeture d’un ensemble d’états. Nous commençons
donc par donner sa définition.

Définition 15 : Soit E un ensemble d’états. On appelle ε-fermeture de E l’ensemble des états

incluant, en plus de ceux de E, tous les états accessibles depuis les états de E par un chemin
étiqueté par le mot ε.

La construction des ε-transitions se fait donc d’une manière récursive. L’étudiant peut, en
guise d’exercice, écrire l’algorithme permettant de construire un tel ensemble.
2.3. Minimisation d’un AEF déterministe 16

Exemple 9 : Considérons l’automate donné par la figure 2.3, calculons un ensemble d’ε-
fermetures :
– ε-fermeture({0}) = {0, 1, 2, 3}
– ε-fermeture({1, 2}) = {1, 2}
– ε-fermeture({3}) = {0, 1, 2, 3}

Algorithme : Déterminisation d’un AEF comportant des ε-transitions

Le principe de cet algorithme repose sur l’utilisation des ε-fermetures qui représenteront
les états du nouvel automate.

1- Partir de l’ε-fermeture de l’état initial (elle représente le nouvel état initial) ;

2- Rajouter dans la table de transition toutes les ε-fermetures des nouveaux
états produits avec leurs transitions ;
3- Recommencer l’étape 2 jusqu’à ce qu’il n’y ait plus de nouvel état ;
4- Tous les ε-fermetures contenant au moins un état final du premier automate
deviennent finaux ;
5- Renuméroter les états en tant qu’états simples.

Exemple 10 : Appliquons maintenant ce dernier algorithme à l’automate de la figure 2.3.

État a b
0,1,2,3 0,1,2,3,4 0,1,2,3
0,1,2,3,4 0,1,2,3,4 0,1,2,3,5,6,7,8
0,1,2,3,5,6,7,8 0,1,2,3,4,5,6,7,8 0,1,2,3,5,6,7,8
0,1,2,3,4,5,6,7,8 0,1,2,3,4,5,6,7,8 0,1,2,3,5,6,7,8

ce qui produit (surprise) l’automate suivant (c’est le même que celui donné par la figure 2.4) :

État a b
0 1 0
1 1 2
2 3 2
3 3 2

2.3 Minimisation d’un AEF déterministe

D’une manière général, moins un automate contient d’états, moins il prendra du temps à
reconnaître un mot (par exemple, en déterminisant un AEF, on tombe le plus souvent sur un
automate comportant plus d’états qu’il n’en faut). Il est donc logique de vouloir minimiser
ce temps en essayant de réduire le nombre d’états. Si on peut trouver une multitude d’auto-
mates pour reconnaître le même langage, on ne peut trouver néanmoins qu’un seul automate
minimal reconnaissant le même langage. La minimisation s’effectue en éliminant les états dits
inaccessibles et en confondant (ou fusionnant) les états reconnaissant le même langage.
2.3. Minimisation d’un AEF déterministe 17

2.3.1 Les états inaccessibles

Définition 16 : Un état est dit inaccessible s’il n’existe aucun chemin permettant de l’atteindre
à partir de l’état initial.

D’après la définition, les états inaccessibles sont improductifs, c’est-à-dire qu’ils ne parti-
ciperont jamais à la reconnaissance d’un mot. Ainsi, la première étape de minimisation d’un
AEF consiste à éliminer ces états. L’étudiant peut, en guise d’exercice, écrire l’algorithme qui
permet de trouver les états inaccessibles d’un AEF.

2.3.2 Les états β-équivalents

Définition 17 : Deux états qi et qj sont dits β-équivalents s’ils permettent d’atteindre un état
final à travers les mêmes mots. On écrit alors : qi β qj .

Par le même mot, on entend que l’on lit la même séquence de symboles pour atteindre
un état final à partir de qi et qj . Par conséquent, ces états reconnaissent le même langage.
La figure 2.5 montre un exemple d’états β-équivalents car l’état qi atteint les états finaux via
le mot a, de même pour l’état qj . L’algorithme de minimisation consiste donc à fusionner
simplement ces états pour n’en faire qu’un.

a
qi qf

a q'f
qj

Figure 2.5 – Exemple d’états β-équivalents

Remarque 1 : La relation β-équivalence est une relation d’équivalence. De plus, ∀x ∈ X

(X étant l’alphabet), δ(qi , x) et δ(qj , x) sont également β-équivalents (puisque qi et qj recon-
naissent le même langage). La relation β-équivalence est donc dite une relation de congruence.

Remarque 2 : Le nombre de classes d’équivalence de la relation β-équivalence est égal au

nombre des états de l’automate minimal car les état de chaque classe d’équivalence recon-
naissent le même langage (ils seront fusionnés).

2.3.3 Minimiser un AEF

La méthode de réduction d’un AEF est la suivante :
1. Nettoyer l’automate en éliminant les états inaccessibles ;
2. Regrouper les états congruents (appartenant à la même classe d’équivalence).
2.3. Minimisation d’un AEF déterministe 18

Algorithme : Regroupement des états congruents

Dans cet algorithme, chaque classe de congruence représentera un état dans l’automate
minimal.

1- Faire deux classes : A contenant les états finaux et B contenant les états non finaux ;
2- S’il existe un symbole a et deux états qi et qj d’une même classe tel que δ(qi , a)
et δ(qj , a) n’appartiennent pas à la même classe, alors créer une nouvelle classe et
séparer qi et qj . On laisse dans la même classe tous les états qui donnent un état
d’arrivée dans la même classe ;
3- Recommencer l’étape 2 jusqu’à ce qu’il n’y ait plus de classes à séparer ;

Les paramètres de l’automate minimal sont, alors, les suivants :

– Chaque classe de congruence est un état de l’automate minimal ;
– La classe qui contient l’ancien état initial devient l’état initial de l’automate minimal ;
– Toute classe contenant un état final devient un état final ;
– La fonction de transition est définie comme suit : soient A une classe de congruence
obtenue, a un symbole de l’alphabet et qi un état qi ∈ A tel que δ(qi , a) est définie. La
transition δ(A, a) est égale à la classe B qui contient l’état qj tel que δ(qi , a) = qj .

Exemple 11 : Soit à minimiser l’automate suivant (les états finaux sont les états 1 et 2 tandis
que l’état 1 est initial) :

État a b
1 2 5
2 2 4
3 3 2
4 5 3
5 4 6
6 6 1
7 5 7

La première étape consiste à éliminer les états inaccessibles, il s’agit juste de l’état 7. Les
étapes de détermination des classes de congruences sont les suivantes :
1. A = {1, 2}, B = {3, 4, 5, 6} ;
2. δ(3, b) = 2 ∈ A,δ(4, b) = 3 ∈ B ainsi il faut séparer 4 du reste de la classe B. Alors, on
crée une classe C contenant l’état 4 ;
3. δ(3, b) = 2 ∈ A, δ(5, b) = 6 ∈ A ainsi il faut séparer 5 du reste de la classe B. Mais inutile
de créer une autre classe puisque δ(4, a) = 5 ∈ B, δ(5, a) = 4 ∈ B et δ(4, b) = 3 ∈ B et
δ(5, b) = 6 ∈ B, il faut donc mettre 5 dans la classe C. C = {4, 5} et B = {3, 6} ;
4. Aucun autre changement n’est possible, alors on arrête l’algorithme.
Le nouvel automate est donc le suivant (l’état initial est A) :

Remarque 3 : L’automate obtenu est minimal et est unique, il ne peut plus être réduit. Si
après réduction on obtient le même automate, alors cela signifie qu’il est déjà minimal.
2.4. Opérations sur les automates 19

Etat a b
A A C
B B A
C C A

2.4 Opérations sur les automates

Notons d’abord que les opérations suivantes ne concernent pas que les AEF, elles peuvent
être étendues à tout automate. Cependant, la complexité de ces opérations augmente inverse-
ment avec le type du langage.

2.4.1 Le complément
Soit A un automate déterministe défini par le quintuplet (X, Q, q0 , F, δ) reconnaissant le
langage L. L’automate reconnaissant le langage inverse (c’est-à-dire X∗ − L) est défini par le
quintuplet (X, Q, q0 , Q − F, δ) (en d’autres termes, il suffit d’inverser les états finaux en états
non finaux et vice-versa).
Cependant, cette propriété ne fonctionne que si l’automate est complet : la fonction δ est
complètement définie pour toute paire (q, a) ∈ Q × X comme le montre les exemples suivants.

Exemple 12 : Soit le langage des mots définis sur l’alphabet {a, b, c} contenant le facteur
ab. Il s’agit ici d’un automate complet, on peut, donc, lui appliquer la propriété précédente
pour trouver l’automate des mots qui ne contiennent pas la facteur ab (notons que l’état 2
du deuxième automate correspond à une sorte d’état d’erreur auquel l’automate se branche
lorsqu’il détecte le facteur ab. On dit que c’est un état improductif étant donné qu’il ne peut
pas générer de mots).

a a,b,c
b,c

a b
0 1 2

c
l'inverse

a a,b,c
b,c

a b
0 1 2

Figure 2.6 – Comment obtenir l’automate du langage complémentaire (d’un automate complet)

Soit maintenant le langage des mots définis sur {a, b, c} contenant exactement deux a
2.4. Opérations sur les automates 20

(figure 2.7). L’automate n’est pas complet, donc, on ne peut pas appliquer la propriété précé-
dente à moins de le transformer en un automate complet. Pour le faire, il suffit de rajouter un
état non final E (on le désignera comme un état d’erreur) tel que δ(2, a) = E.

b,c b,c b,c

a a
0 1 2

l'inverse? (pas
vraiment)

b,c b,c b,c

a a
0 1 2

Figure 2.7 – Si l’automate n’est pas complet, on ne peut pas obtenir l’automate du langage inverse.
L’automate obtenu reconnaît les mots contenant au plus 1 a.

Considérons à la fin l’automate de la figure 2.8. Les deux automates reconnaissent le mot
a ce qui signifie que les deux automates ne reconnaissent pas des langages complémentaires.

Remarque 4 : Le fait qu’un AEF ne soit pas déterministe ne représente pas un obstacle pour
trouver l’automate du langage inverse. En effet, on pourra toujours le construire en procédant
à une transformation. Laquelle ?

Remarque 5 : L’algorithme de déduction de l’automate du complémentaire peut en réalité

être appliqué à un automate incomplet. Il suffit juste de le transformer en un automate complet
et de lui appliquer, ensuite, l’algorithme. Comment rendre un automate complet ?

2.4.2 L’opération d’entrelacement

Nous verrons ici le cas simple de l’entrelacement d’un langage avec un symbole. Soit L un
langage accepté par un AEF (X, Q, q0 , F, δ). On note par Q ′ l’ensemble des états de Q aux-
quels on rajoute prime ( ′ ), par F ′ l’ensemble des états de F auxquels on rajoute ′ . L’automate


acceptant le langage L a est donné par (X, Q ∪ Q ′ , q0 , F ′ , δ ′ ) tel que :
– δ ′ (qi , x) = δ(qi , x), x 6= a et qi ∈ Q ;
– δ ′ (qi , x) = (δ(qi , x)) ′ , qi ∈ Q ′ ;
– δ ′ (qi , a) = qi′ .
Exemple : voir la figure 2.9.
2.4. Opérations sur les automates 21

a 1
0

a
a,b

l'inverse?

a 1
0

a
a,b

Figure 2.8 – Si l’automate n’est pas déterministe, on ne peut pas trouver l’automate du langage
complémentaire.

Figure 2.9 – Exemple d’entrelacement

2.4. Opérations sur les automates 22

2.4.3 Produit d’automates

Définition 18 : Soit A = (X, Q, q0 , F, δ) et A ′ = (X ′ , Q ′ , q0′ , F ′ , δ ′ ) deux automates à états

finis. On appelle produit des deux automates A et A ′ l’automate A ′′ (X ′′ , Q ′′ , q0′′ , F ′′ , δ ′′ ) défini
comme suit :
– X ′′ = X ∪ X ′ ;
– Q ′′ = Q × Q ′ ;
– q0′′ = (q0 , q0′ ) ;
– F ′′ = F × F ′ ;
– δ ((q, q ′ ) , a) = (δ(q, a), δ(q ′ , a))

Cette définition permet de synchroniser la reconnaissance d’un mot par les deux auto-
mates. On pourra facilement démontrer que si w est un mot reconnu par A ′′ alors il l’est par
A, ceci est également le cas pour l’automate A ′ . Ainsi, si L(A) est le langage reconnu par A
et L(A ′ ) est le langage reconnu par le langage A ′ alors l’automate A ′′ reconnaît l’intersection
des deux langages : L(A) ∩ L(A ′ ).

Exemple 13 : Considérons la figure 2.10. L’automate (1) reconnaît les mots sur {a, b, c} conte-
nant deux a, l’automate (2) reconnaît les mots sur {a, b, c} contenant deux b, l’automate (3)
représente le produit des deux automates. Remarquons que dans l’automate (3), tout chemin
qui mène de l’état initial vers l’état final passe forcément par deux a et deux b (tout ordre
est possible). Or, ceci est exactement le langage résultant de l’intersection des deux premiers
langages.

(1) a,b,c a,b,c a,b,c

a,b,c a,b,c a,b,c

b b
0,0' 0,1' 0,2'
a a a
0 1 2 a a
a,b,c
b b
1,0' 1,1' 1,2'
(2)
a,b,c a a,b,c
a,b,c a,b,c a,b,c a a
b b
2,0' 2,1' 2,2'
b b
0' 1' 2'

a,b,c a,b,c a,b,c

(3)

Figure 2.10 – Exemple d’intersection de produit d’automates

2.4.4 Le langage miroir

Soit A = (X, Q, q0 , F, δ) un automate reconnaissant le langage L(A). L’automate qui recon-
naît le langage (L(A))R est reconnu par l’automate AR = (X, Q, F, {q0 }, δR ) tel que : δR (q ′ , a) =
2.4. Opérations sur les automates 23

q si δ(q, a) = q ′ .
En d’autres termes, il suffit juste d’inverser les sens des arcs de l’automate et le statut
initial/final des états initiaux et finaux. Notons, par ailleurs, que l’automate AR peut contenir
plusieurs états initiaux ce qui signifie qu’il est le plus souvent non déterministe. Pour éliminer
le problème des multiples états initiaux, il suffit de rajouter un nouvel état initial et de le
raccorder aux anciens états finaux par des ε-transitions.

Nous pouvons également énoncer les résultats suivants :

– Si L et M sont deux langages reconnus pas deux AEF, alors L + M est également reconnu
par un AEF ;
– Si L et M sont deux langages reconnus par deux AEF, alors L.M est également reconnu
par un AEF ;
– Si L est un langage reconnu par un AEF, alors L∗ est également reconnu par un AEF ;
Le chapitre suivant traite des langages réguliers et des expressions régulières. On y abor-
dera les opérations précédentes avec plus de détails étant donné qu’elles représentent les
opérations de base lorsqu’on travaille avec les expressions régulières.
2.5. Exercices de TD 24

2.5 Exercices de TD

Exercice 11 : Déterminisez et minimisez si nécessaire l’automate suivant :

a b

a
0 1

a a
b
2

Exercice 12 : Déterminisez et minimisez si nécessaire l’automate suivant :

b

a,ε
0 1

b a b

ε
3 2
b a

Exercice 13 : Minimiser l’automate suivant (l’état initial est 1, les états finaux sont {3, 6, 8}) :

État a b c
1 2 3 4
2 1 5 6
3 1 5 6
4 2 6 1
5 4 7 8
6 4 5 3
7 4 5 3
8 9 3 6
9 7 3 9

Exercice 14 : Donnez les automates à états finis qui reconnaissent les langages suivants :
– Tous les mots sur {a, b, c} ;
– Tous les mots sur {a, b, c} qui se terminent avec un symbole différent de celui du début ;
– Tous les mots sur {a, b, c} qui contiennent le facteur ab ;
– Tous les mots sur {a, b, c} qui ne contiennent pas le facteur aba ;
– Tous les mots sur {a, b, c} qui ne contiennent pas le facteur aac ;
– Tous les mots sur {a, b, c} qui ne contiennent ni le facteur aba ni le facteur aac ;
2.5. Exercices de TD 25

– Tous les mots sur {a, b, c} tels que toutes les occurrences de c précèdent celle de b tout
en ayant deux a.

Exercice 15 : Donnez l’automate qui reconnaît tous les mots sur {a} qui contiennent un
nombre pair de a. En déduire l’automate qui reconnaît le langage de tous les mots sur {a, b}
contenant un nombre pair de a et un nombre pair de b.

Exercice 16 : Considérons l’ensemble des nombres binaires, donnez les automates qui recon-
naissent :
– Les nombres multiples de 2 ;
– Les nombres multiples de 4 ;
En déduire l’automate qui reconnaît les multiples des nombres de la forme 2n (n > 1). Si n est
fixe, peut-on concevoir un automate qui reconnaît les multiples de tous les nombres binaires
de la forme 2i (0 < i 6 n) et qui permet de simuler le calcul de i ? Si oui, donnez l’automate,
si non dites pourquoi ?

Exercice 17 : Donnez l’automate qui reconnaît les nombres binaires multiples de 3. Donnez
ensuite deux façons pour construire l’automate qui reconnaît les multiples de 6.

Exercice 18 : Soit un mobile pouvant bouger dans un environnement sous forme d’une
matrice {0, 1, 2, 3} × {0, 1, 2, 3} selon la figure suivante.

4 Position possible

Zone autorisée 3

2
H
G
1 D
B
0
0 1 2 3 4

Les mouvements possibles sont D (droite), G (gauche), H (haut) et B (bas). Le mobile prend
ses ordres sous forme de mots composés sur l’alphabet {D, G, H, B} (tout déplacement se fait
d’une unité). Par exemple, si le mobile se trouve sur le point (0, 0), alors le mot DHHG va situer
le mobile sur le point (0, 2). Ainsi, on peut parler de langages de déplacements permettant
d’effectuer telle ou telle tâche. Donnez, si possible, les automates des déplacements (langages)
suivants (on suppose que le mobile se trouve, au départ, au point (0, 0)) :
– Tout chemin assurant que le mobile reste dans la zone autorisée ;
– Les chemins qui n’entrent pas dans le carré {1, 2} × {1, 2} ;
– Les déplacements qui font revenir le mobile vers l’origine des coordonnées.

Exercice 19 : Donnez un automate reconnaissant une date de la forme jour/mois. Faites

2.5. Exercices de TD 26

attention aux dates invalides du type 30/02 (on considère que la date 29/02 est valide).

Exercice 20 : Donnez les algorithmes permettant d’effectuer les opérations suivantes :

– Déterminer les états inaccessibles d’un automate ;
– Transformer un AEF incomplet en un AEF complet.

Exercice 21 : Donnez un automate déterministe reconnaissant les nombres réels en langage

Pascal.

Exercice 22 : Donnez l’automate qui reconnaît les mots qui contiennent un a dans tout facteur
de longueur n > 1 (voir l’exercice 6).

Exercice 23 : Soit u un mot non vide défini sur un alphabet donné, donnez un algorithme
qui permet de construire un automate des mots qui ne contiennent pas le facteur u. Donnez
également un algorithme qui construit un automate des mots qui ne contiennent ni la facteur
u ni la facteur v (v étant un autre mot non vide différent de u).

Exercice 24 : Dans un environnement virtuel, un robot se déplace en suivant les ordres donnés
sous forme de mots (pour simplifier, on suppose que l’alphabet utilisé est égal à {a, b}). Par
exemple, on peut lui donner l’ordre abba pour lui ordonner d’aller à l’endroit ayant comme
nom abba. Si le mot contient une séquence non répertoriée, alors l’emplacement du robot est
indéterminé.
– Soient les emplacements ab et ba. Construire un automate déterministe permettant
d’aller à deux états finaux différents selon la séquences lue (par exemple, si l’automate
vient de lire ab alors il se trouve dans l’état 0, s’il lit ba alors il doit aller à l’état 1) ;
– Refaites la même chose avec les emplacements {aa, bb} et {aba, abb} ;
– Soit un automate qui reconnaît un seul emplacement u (vous pouvez considérer les
automates précédents), quelle caractéristique peut on donner au langage reconnu par
cet automate. En déduire une méthode permettant de construire l’automate qui permet
de reconnaître deux emplacements distincts u et v.
 Chapitre 3

Les langages réguliers

Les langages réguliers sont les langages générés par des grammaires de type 3 (ou en-
core grammaires régulières). Ils sont reconnus grâce aux automates à états finis. Le terme
régulier vient du fait que les mots de tels langages possèdent une forme particulière pouvant
être décrite par des expressions dites régulières. Ce chapitre introduit ces dernières et établit
l’équivalence entre les trois représentation : expression régulière, grammaire régulière et AEF.

3.1 Les expressions régulières E.R

Définition 19 : Soit X un alphabet quelconque ne contenant pas les symboles {∗, +, |, ., (, )}.
Une expression régulière est un mot défini sur l’alphabet X ∪ {∗, +, |, ., (, )} permettant de
représenter un langage régulier de la façon suivante :
– L’expression régulière ε dénote le langage vide (L = {ε}) ;
– L’expression régulière a (a ∈ X) dénote le langage L = {a} ;
– Si r est une expression régulière qui dénote L alors (r)∗ (resp. (r)+ ) est l’expression
régulière qui dénote L∗ (resp. L+ ) ;
– Si r est une expression régulière dénotant L et s une expression régulière dénotant L ′
alors (r)|(s) est une expression régulière dénotant L + L ′ . L’expression régulière (r).(s)
(ou simplement (r)(s)) dénote le langage L.L ′ .

Les expressions régulières sont également appelées expressions rationnelles. L’utilisation

des parenthèses n’est pas obligatoire si l’on est sûr qu’il n’y ait pas d’ambiguïté quant à
l’application des opérateurs ∗, +, |, .. Par exemple, on peut écrire (a)∗ ou a∗ puisque l’on est
sûr que ∗ s’applique juste à a. Par ailleurs, on convient à utiliser les priorités suivantes pour
les différents opérateurs : 1)∗, +, 2). et 3)|.

Exemple 14 :
1. a∗ : dénote le langage régulier an (n > 0) ;
2. (a|b)∗ : dénote les mots dans lesquels le symbole a ou b se répètent un nombre quel-
conque de fois. Elle dénote donc le langage de tous les mots sur {a, b} ;
3. (a|b)∗ ab(a|b)∗ : dénote tous les mots sur {a, b} contenant le facteur ab.

27
3.2. Les langages réguliers, les grammaires et les automates à états finis 28

3.1.1 Expressions régulières ambiguës

Définition 20 : Une expression régulière est dite ambiguë s’il existe au moins mot pouvant
être mis en correspondance avec l’expression régulière de plusieurs façons.

Cette définition fait appel à la correspondance entre un mot et une expression régulière.
Il s’agit, en fait, de l’opération qui permet de dire si le mot appartient au langage décrit par
l’expression régulière. Par exemple, prenons l’expression régulière a∗ b∗ . Soit à décider si le
mot aab est décrit ou non par cette expression. On peut écrire :

aa |{z}
|{z} b
a∗ b∗

Ainsi, le mot est décrit par cette E.R. Il n’y a qu’une seule façon qui permet de le faire corres-
pondre. Ceci est valable pour tous les mots de ce langage. L’E.R n’est donc pas ambiguë.
Considérons maintenant l’expression (a|b)∗ a(a|b)∗ décrivant tous les mots sur {a, b} conte-
nant le facteur a. Soit à faire correspondre le mot aab, on a :

abaab = ab .a. |{z}

|{z} ab
(a|b)∗ (a|b)∗
abaab = aba b
|{z} .a. |{z}
(a|b)∗ (a|b)∗

Il existe donc au moins deux façons pour faire correspondre aab à l’expression précédente,
elle est donc ambiguë.
L’ambiguïté pose un problème quant à l’interprétation d’un mot. Par exemple, supposons
que, dans l’expression (a|b)∗ a(a|b)∗ , l’on veut comparer la partie à gauche du facteur a à la
partie droite du mot. Selon la méthode de correspondance, le résultat est soit vrai ou faux ce
qui est inacceptable dans un programme cohérent.

3.1.2 Comment lever l’ambiguïté d’une E.R ?

Il n’existe pas une méthode précise pour lever l’ambiguïté d’une E.R. Cependant, on peut
dire que cette opération dépend de ce que l’on veut faire avec l’E.R ou plutôt d’une hypothèse
de reconnaissance. Par exemple, on peut décider que le facteur fixe soit le premier a du mot à
reconnaître ce qui donne l’expression régulière : b∗ a(a|b)∗ . On peut également supposer que
c’est le dernier a du mot à reconnaître ce qui donne l’expression régulière (a|b)∗ ab∗ . La série
de TD propose quelques exercices dans ce sens.

3.2 Les langages réguliers, les grammaires et les automates à états

finis
Le théorème suivant établit l’équivalence entre les AEF, les grammaires régulières et les
expressions régulières :

Théorème 2 : (Théorème de Kleene) Soient Λreg l’ensemble des langages réguliers (générés
par des grammaires régulières), Λrat l’ensemble des langages décrits par toutes les expres-
sions régulières et ΛAEF l’ensemble de tous les langages reconnus par un AEF. Nous avons,
3.2. Les langages réguliers, les grammaires et les automates à états finis 29

alors, l’égalité suivante :

Λreg = Λrat = ΛAEF

Le théorème annonce que l’on peut passer d’une représentation à une autre du fait de
l’équivalence entre les trois représentations. Cette section explique donc comment passer
d’une représentation à une autre.

3.2.1 Passage de l’automate vers l’expression régulière

Soit A = (X, Q, q0 , F, δ) un automate à états fini quelconque. On appelle Li le langage
reconnu par l’automate si son état initial était qi . Par conséquent, trouver le langage reconnu
par l’automate revient à trouver L0 étant donné que la reconnaissance commence à partir
de l’état initial q0 . L’automate permet d’établir un système d’équations aux langages de la
manière suivante :
– si δ(qi , a) = qj alors on écrit : Li = aLj ;
– si qi ∈ F, alors on écrit : Li = ε
– si Li = α et Li = β alors on écrit : Li = α|β ;
Il suffit ensuite de résoudre le système en précédant à des substitutions et en utilisant la
règle suivante : la solution de l’équation L = αL|β (ε ∈ / α) est le langage L = α∗ β (attention ! si
vous obtenez L = αL alors c’est la preuve d’une faute de raisonnement).

Exemple 15 : Soit l’automate donné par la figure suivante :

a b 1
a

0
2
b
a

Trouvons le langage reconnu par cet automate. Le système d’équations est le suivant :
– 1) L0 = aL0 |bL1 ;
– 2) L1 = bL1 |aL2 ;
– 3) L2 = aL2 |bL0 |ε
Appliquons la deuxième règle sur les équations, on obtient alors après substitutions :
– 4) L0 = a∗ bL1 ;
– 5) L1 = b∗ aL2 = b∗ a+ bL0 |b∗ a+ ;
– 6) L2 = a∗ bL0 |a∗
En remplaçant 5) dans 4) on obtient : L0 = a∗ b+ a+ bL0 |a∗ b+ a+ ce qui donne L0 = (a∗ b+ a+ b)∗ a∗ b+ a+
(remarquez que l’on pouvait déduire la même chose à partir de l’automate...).

3.2.2 Passage de l’expression régulière vers l’automate

Il existe deux méthodes permettant de réaliser cette tâche. La première fait appel à la
notion de dérivée tandis que la deuxième construit un automate comportant des ε-transitions
3.2. Les langages réguliers, les grammaires et les automates à états finis 30

en se basant sur les propriétés des langages réguliers.

Dérivée d’un langage

Définition 21 : Soit w un mot défini sur un alphabet X. On appelle dérivée de w par rapport
à u ∈ X∗ le mot v ∈ X∗ tel que w = uv. On note cette opération par : v = w||u.

On peut étendre cette notion aux langages. Ainsi la dérivée d’un langage par rapport à un
mot u ∈ X∗ est le langage L||u = {v ∈ X∗ |∃w ∈ L : w = uv}.

Exemple 16 :
– L = {1, 01, 11}, L||1 = {ε, 1}, L||0 = {1}, L||00 = ∅

Propriétés des dérivées

P Pn
– ( n i=1 Li )||u = i=1 (Li ||u) ;
– L.L ||u = (L||u).L + f(L).(L ′ ||u) tel que f(L) = {ε} si ε ∈ L et f(L) = ∅ sinon ;
′ ′

– (L∗ )||u = (L||u)L∗ .

Méthode de construction de l’automate par la méthode des dérivées

Soit r une expression régulière (utilisant l’alphabet X) pour laquelle on veut construire
un AEF. L’algorithme suivant donne la construction de l’automate :
1. Dériver r par rapport à chaque symbole de X ;
2. Recommencer 1) pour chaque nouveau langage obtenu jusqu’à ce qu’il n’y ait plus
de nouveaux langages ;
3. Chaque langage obtenu correspond à un état de l’automate. L’état initial corres-
pond à r. Si ε appartient à un langage obtenu alors l’état correspondant est final ;
4. si Li ||a = Lj alors on crée une transition entre l’état associé à Li et l’état associé à Lj
et on la décore par a.

Exemple 17 : Considérons le langage (a|b)∗ a(a|b)∗ . On sait que :

– (a|b)||a = ε donc (a|b)∗ ||a = (a|b)∗
Commençons l’application de l’algorithme :
– [(a|b)∗ a(a|b)∗ ]||a = ((a|b)∗ a(a|b)∗ )|(a|b)∗ ;
– [(a|b)∗ a(a|b)∗ ]||b = (a|b)∗ a(a|b)∗ ;
– [((a|b)∗ a(a|b)∗ )|(a|b)∗ ]||a = ((a|b)∗ a(a|b)∗ )|(a|b)∗ ;
– [((a|b)∗ a(a|b)∗ )|(a|b)∗ ]||b = ((a|b)∗ a(a|b)∗ )|(a|b)∗ ;
Il n’y a plus de nouveaux langages, on s’arrête alors. L’automate comporte deux états q0
(associé à (a|b)∗ a(a|b)∗ ) et q1 (associé à ((a|b)∗ a(a|b)∗ )|(a|b)∗ ), il est donné par la table
suivante (l’état initial est q0 et l’état q1 est final) :
État a b
q0 q1 q0
q1 q1 q1
3.2. Les langages réguliers, les grammaires et les automates à états finis 31

Méthode de Thompson
La méthode de Thompson permet de construire un automate en procédant à la décompo-
sition de l’expression régulière selon les opérations utilisées. Soit r une E.R, alors l’algorithme
à utiliser est le suivant :
– Si r = a (un seul symbole) alors l’automate est le suivant :
a

– Si r = st alors il suffit de trouver l’automate As qui reconnaît s et l’automate At qui

reconnaît t. Il faudra, ensuite relier chaque état final de As à l’état initial de At par une
ε-transition. Les états finaux de As ne le sont plus et l’état initial de At ne l’est plus :
s t

... ε ...
ε
... ε ...

– Si r = s|t alors il suffit de créer un nouvel état initial et le relier avec des ε-transitions
aux états initiaux de Ar et As qui ne le sont plus :
s

...

...
ε

t
ε
...

...

– Si r = s+ alors il suffit de relier les états finaux de As par des ε-transitions à son état
initial :
s
ε
...
ε
...
ε

– Si r = s∗ alors il suffit de relier les états finaux de As par des ε-transitions à son état
initial puis relier ce dernier à chacun des états finaux par des ε-transitions :
3.2. Les langages réguliers, les grammaires et les automates à états finis 32

s
ε ε
...
ε
ε
...
ε ε

Exemple 18 : Soit à construire l’automate du langage (a|b)∗ a(a|b)∗ , la méthode de Thompson

donne l’automate suivant :

ε ε
a a
ε ε ε
ε a ε ε
ε ε
b ε b
ε ε

ε ε

3.2.3 Passage de l’automate vers la grammaire

Du fait de l’équivalence des automates à états finis et les grammaires régulières, il est pos-
sible de passer d’une forme à une autre. Le plus facile étant le passage de l’automate vers
la grammaire. Le principe de correspondance entre automates et grammaires régulières est
très intuitif : il correspond à l’observation que chaque transition dans un automate produit
exactement un symbole, de même que chaque dérivation dans une grammaire régulière nor-
malisée. Soit A = (X, Q, q0 , F, δ) un AEF, la grammaire qui génère le langage reconnu par A est
g = (V, N, S, R) :
– V = X;
– On associe à chaque état de Q un non terminal. Ceci permet d’avoir autant de non-
terminaux qu’il existe d’états dans A ;
– L’axiome S est le non-terminal associé à l’état initial q0 ;
– Soit A le non terminal associé à qi et B le non-terminal associé à qj , si δ(qi , a) = qj alors
la grammaire possède la règle de production : A → aB ;
– Si qi est final et A est le non-terminal associé à qi alors la grammaire possède la règle
de production : A → ε.
Il s’agit ici d’une grammaire régulière à droite. Un exercice de TD propose de trouver une
méthode permettant de construire la grammaire régulière à gauche. Notons, par le passage,
que l’on s’intéresse généralement à une forme normalisée des grammaires régulières. Celle-ci
est définie comme suit : soit G = (V, N, S, R) une grammaire régulière à droite, elle est dite
normalisée si toutes les règles de production sont de l’une des formes suivantes :
– A → a, A ∈ N, a ∈ V ;
– A → aB, A, B ∈ N, a ∈ V ;
– A → ε, A ∈ N
Voir la paragraphe suivant pour transformer une grammaire régulière en sa forme normale.
3.3. Propriétés des langages réguliers 33

3.2.4 Passage de la grammaire vers l’automate

D’après la section précédente, il existe une forme de grammaires régulières pour lesquelles
il est facile de construire l’AEF correspondant. En effet, soit G = (V, N, S, R) une grammaire
régulière à droite, si toutes les règles de production sont de la forme : A → aB ou A → B
(A, B ∈ N, a ∈ V ∪ {ε}) alors il suffit d’appliquer l’algorithme suivant :
1. Associer un état à chaque non terminal de N ;
2. L’état initial est associé à l’axiome ;
3. Pour chaque règle de production de la forme A → ε, l’état qA est final ;
4. Pour chaque règle de production de la forme A → a (a ∈ V), alors créer un nouvel état
final qf et une transition partant de l’état qA vers l’état qf avec l’entrée a ;
5. Pour chaque règle A → aB alors créer une transition partant de qA vers l’état qB en
utilisant l’entrée a ;
6. Pour chaque règle A → B alors créer une ε-transition partant de qA vers l’état qB ;
Cependant, cet algorithme ne peut pas s’appliquer à toutes les grammaires régulières. On
peut néanmoins transformer toute grammaire régulière à la forme donnée ci-dessus. L’algo-
rithme de transformation est le suivant. Soit G = (V, N, S, R) une grammaire régulière :
1. Pour chaque règle de la forme A → wB (A, B ∈ N et w ∈ V∗) tel que |w| > 1, créer
un nouveau non-terminal B ′ et éclater la règle en deux : A → aB ′ et B ′ → uB tel que
w = au et a ∈ V ;
2. Pour chaque règle de la forme A → w (A ∈ N et w ∈ V∗) tel que |w| > 1, créer un
nouveau non-terminal B ′ et éclater la règle en deux : A → aB ′ et B ′ → u tel que w = au
et a ∈ V ;
3. Recommencer 1) et 2) jusqu’à ce qu’il n’y ait plus de nouveaux non terminaux ;
Enfin, l’élimination des règles A → B (A, B ∈ N), on applique l’algorithme suivant (il faut bien
entendu enlever toute règle de la forme A → A) :
1. Pour chaque règle A → B tel que B → β1 |β2 |...|βn
– Rajouter une règle A → β1 |β2 |...|βn
– Supprimer la règle A → B
2. Refaire l’étape 1) jusqu’à ce qu’il n’y ait plus de règles de la forme A → B

Exemple 19 : Soit la grammaire régulière G = ({a, b}, {S, T }, S, {S → aabS|bT , T → aS|bb}). Le

processus de transformation est le suivant :
– Éclater S → aabS en S → aS1 et S1 → abS ;
– Éclater S1 → abS en S1 → aS2 et S2 → bS ;
– Éclater T → bb en T1 → bT1 et T1 → b ;

3.3 Propriétés des langages réguliers

3.3.1 Stabilité par rapport aux opérations sur les langages
Les langages réguliers sont stables par rapport aux opérations de l’union, l’intersection, le
complémentaire, la concaténation et la fermeture de Kleene. La démonstration de ce résultat
3.3. Propriétés des langages réguliers 34

est très simple. Soient L et M deux langages réguliers désignés respectivement par les E.R r
et s et respectivement reconnus par les automates Ar et As . Étant donnée l’équivalence entre
les langages réguliers et les AEF, nous avons :
– L + M est régulier : l’AEF correspondant s’obtient en utilisant l’algorithme de construc-
tion de l’automate de reconnaissance de l’E.R r|s ;
– L ∩ M est régulier : l’AEF correspondant s’obtient en calculant le produit de Ar et As
(voir le chapitre précédent) ;
– L est régulier : l’AEF correspondant s’obtient en rendant l’automate Ar complet puis en
inversant le statut final/non final des états (voir le chapitre précédent) ;
– LR est régulier : l’AEF correspondant s’obtient en inversant le sens des arcs dans Ar et
en inversant le statut initial/final des états (voir le chapitre précédent) ;
– L.M est régulier : l’AEF correspondant s’obtient en utilisant l’algorithme de construction
de l’automate de r.s ;
– L∗ (resp. L+ ) est régulier : l’AEF correspondant s’obtient en utilisant l’algorithme de
construction de l’automate de r∗ (resp. r+ ) ;

3.3.2 Lemme de la pompe

Dans cette section, nous présentons les critères permettant d’affirmer si un langage est
régulier ou non. Avant toute discussion, on peut déjà annoncer que tout langage fini est un
langage régulier. En effet, la construction d’un AEF reconnaissant ce type de langages est
facile. L’étudiant peut en guise d’exercice trouver une méthode permettant de trouver l’AEF
d’un langage fini quelconque, sa grammaire ainsi que l’E.R qui le représente.
A présent, nous allons annoncer un critère dont la vérification permet de juger si un lan-
gage n’est pas régulier. Il s’agit en fait d’une condition suffisante et non nécessaire pour qu’un
langage soit régulier. La démonstration de ce résultat sort du cadre du cours.

Proposition 2 : Soit L un langage régulier infini défini sur l’alphabet X. Il existe alors un
entier n tel que pour tout mot w ∈ L et |w| > n, il existe x, z ∈ X∗ et y ∈ X+ tels que :
– w = xyz ;
– |xy| 6 n ;
– xyi z ∈ L pour tout i > 0.

Il est à noter que cette condition est suffisante et non nécessaire. Il existe, en effet, des
langages non réguliers vérifiant ce critère. Il existe néanmoins une condition nécessaire et
suffisante que l’on va énoncer après avoir présenté un exemple d’utilisation du lemme de la
pompe.

Exemple 20 : Soit le langage L = ak bl (ou encore a∗ b∗ , il s’agit donc d’un langage régulier).
Prenons n = 1 et vérifions le critère de la pompe. Soit un mot w = ak bl (k + l > 1). Si k > 0
alors il suffit de prendre x = ak−1 , y = a et z = bl , ainsi tout mot de la forme xyi z = ak+i−1 bl
appartient au langage. Si k = 0 alors il suffit de prendre x = ε, y = b et z = bl−1 pour vérifier
le critère de la pomme.

Exemple 21 : Soit le langage L = ak bk (avec k > 0) 3 . Supposons que le langage est régulier
et appliquons le lemme de la pompe. Supposons que l’on a trouvé n qui vérifie le critère,
3. Attention, l’expression ak bk n’est pas régulière.
3.3. Propriétés des langages réguliers 35

ceci implique que pour tout mot w ∈ L, on peut le décomposer en trois sous-mots x, y et z
tel que : |xy| 6 n, y 6= ε et xyi z ∈ L. Considérons le mot an+1 bn+1 , toute décomposition
de ce mot produire les mots x = aj , y = al et z = an+1−j−l bn+1 , l > 0 (si xy contient n
symboles alors x et y ne contiennent que des a étant donné qu’il y a (n + 1) a). Maintenant,
le lemme de la pompe stipule que xyi z ∈ L pour tout i > 0 donc tout mot de la forme
aj ail an+1−j−l bn+1 = a(i−1)l+n+1 bn+1 appartient à L. Pour i = 2 la borne inférieure de
(i − 1)l est 1, ce qui signifie que le nombre de a est différent du nombre de b. Contradiction.
Donc, le langage ak bk n’est pas régulier.

Exemple 22 : Soit maintenant soit L ⊂ b∗ un langage non régulier arbitraire. Le langage :

a+ L|b∗

satisfait le lemme de la pompe. Il suffit de prendre avec les notations du lemme, n = 1. Cet
exemple illustre donc le fait que le lemme précédent ne constitue pas une condition nécessaire
pour décider de la régularité d’un langage.

Proposition 3 :

Soit L un langage infini défini sur l’alphabet X. L est régulier si et seulement s’il existe un
entier n > 0 tel que pour tout mot w ∈ X∗ et |w| > n, il existe x, z ∈ X∗ et y ∈ X+ tels que :
– w = xyz ;
– ∀u ∈ X∗ : wv ∈ X∗ ⇔ xyi zu ∈ L.
3.4. Exercices de TD 36

3.4 Exercices de TD

Exercice 25 : Donnez une description de chacune des E.R suivantes, puis donnez leurs
équivalentes UNIX :
– a(a|b)∗ (b|ε) ;
– (aaa)∗ ;
– (a|ab|abb)∗
– a(a|b)∗ (aa|bb)+
– (a|ab)∗

Exercice 26 : Donnez les expressions régulières UNIX suivantes :

– Les identificateurs en C ;
– Les noms de fichiers en DOS ;
– Les nombres entiers multiples de 5 en base 10 ;
– Les mots sur {a, b, c} contenant la facteur a1000 .

Exercice 27 : Donnez une expression régulière pour chacun des langages suivants. En déduire
à chaque fois l’automate correspondant en utilisant la méthode de Thompson ou celle des
dérivées. Donnez leurs équivalentes UNIX.
– Tous les mots sur {a, b, c} commençant par a ;
– Tous les mots sur {a, b} commençant par un symbole différent de leur dernier symbole ;
– Tous les mots sur {a, b, c} contenant exactement deux a ;
– Tous les mots sur {a, b, c} contenant au moins deux a ;
– Tous les mots sur {a, b, c} contenant au plus deux a ;
– Tous les mots sur {a, b, c} ne contenant pas la facteur ab ;
– Tous les mots sur {a, b, c} ne contenant pas le facteur aac ;
– Tous les entiers (en base dix) multiples de 5.

Exercice 28 : Soit l’automate suivant :

b
2
a b
0 1 a
b
3
b

Trouvez le langage reconnu par cet automate ainsi qu’une grammaire régulière qui le
génère.

Exercice 29 : Soit l’automate suivant :

3.4. Exercices de TD 37

b,c a

a a
0 1 2

b,c
b

1. Trouvez le langage régulier reconnu par cet automate ;

2. Trouvez l’automate du langage complémentaire et déduire son expression régulière.

Exercice 30 : Soit le grammaire régulière : G = ({a, b}, {S, T }, S, {S → abS|aS|bT |ε, T →

baT |bT |aS|ε}). Trouver l’automate reconnaissant le langage généré par cette grammaire puis
en déduire son expression régulière.

Exercice 31 : En utilisant le lemme de la pompe, dites si les langages suivants sont réguliers.
Si le critère de la pompe est vérifié, donnez un AEF ou une grammaire régulière générant le
langage pour être sûr de la régularité :
– an bm ,n > 0, m > 0 ;
– a2n+1 , n > 0 ;
– an bm , n, m > 0 et n + m est pair ;
– a2n bn , n > 0
2
– an , n > 0 ;
2
– bm an + ak , n, k > 0, m > 0

Exercice 32 : Donnez une expression régulière décrivant les langages suivants :

– tous les mots sur {a, b} où chaque a est précédé d’un b ;
– tous les mots sur {a, b} contenant à la fois les facteurs aa et bb ;
– tous les mots sur {a, b} contenant soit aa soit bb mais pas les deux à la fois ;
– tous les mots sur {a, b} ne contenant pas deux a consécutifs ;
– tous les mots sur {a, b, c} où le nombre de a est multiple de 3 ;
–

Exercice 33 : Dans le cours, nous avons vu l’algorithme permettant de déduire une grammaire
régulière à droite à partir d’un AEF. Proposez un algorithme permettant de déduire une
grammaire régulière à gauche à partir d’un AEF.
 Chapitre 4

Les langages algébriques

Malgré la panoplie d’algorithmes existants pour travailler sur les automates à états finis,
ceux-là sont limités aux seuls langages réguliers. Par exemple, dans le chapitre précédent,
nous avons montré que le langage {an bn |n > 0} n’est pas régulier et, par conséquent, ne peut
pas être reconnu par un AEF. Ce chapitre élargit un peu le champ d’étude en s’intéressant aux
langages algébriques qui représentent la couche qui suit immédiatement celle des langages
réguliers dans la hiérarchie de Chomsky. Remarquons, cependant, que le niveau de complexité
est inversement proportionnel au type du langage et, par conséquent, le nombre d’algorithmes
existants tend à diminuer en laissant la place à plus d’intuition.

4.1 Les automates à piles

Les automates à piles sont une extension des automates à états finis. Ils utilisent une (et
une seule) pile pour reconnaître les mots en entrée.

Définition 22 : Un automate à pile est défini par le sextuple A = (X, Π, Q, q0 , F, δ) tel que :
– X est l’ensemble des symboles formant les mots en entrée (alphabet des mots à recon-
naître) ;
– Π est l’ensemble des symboles utilisés pour écrire dans la pile (l’alphabet de la pile). Cet
alphabet doit forcément inclure le symbole ⊲ signifiant que la pile est vide ;
– Q est l’ensemble des états possibles ;
– q0 est l’état initial ;
– F est l’ensemble des états finaux (F 6= ∅, F ⊆ Q) ;
– δ est une fonction de transition permettant de passer d’un état à un autre :
δ : Q × (X ∪ {ε}) × Π 7→ Q × (Π − {⊲})∗
δ(qi , a, b) = (qj , c) ou ∅ (∅ signifie que la configuration n’est pas prise en charge)
b est le sommet de la pile et c indique le nouveau contenu de la pile relativement
à ce qu’il y avait

Par conséquent, tout automate à états fini est en réalité un automate à pile à la seule
différence que la pile du premier reste vide ou au mieux peut être utilisée dans une certaine
limite.

Une configuration d’un automate à pile consiste donc à définir le triplet (q, a, b) tel que q
est l’état actuel, a et le symbole actuellement en lecture et b est le sommet actuel de la pile.

38
4.1. Les automates à piles 39

Lorsque b = " ⊲ ", alors la pile est vide.

Les exemples suivants illustrent comment peut-on interpréter une transition :
– δ(q0 , a, ⊲) = (q1 , B⊲) signifie que si l’on est dans l’état q0 , si le symbole actuellement lu
est a et si la pile est vide alors passer à l’état q1 et empiler le symbole B ;
– δ(q0 , a, A) = (q1 , BA) signifie que si l’on est dans l’état q0 , si le symbole actuellement lu
est a et si le sommet de la pile est A alors passer à l’état q1 et empiler le symbole B ;
– δ(q0 , ε, A) = (q1 , BA) signifie que si l’on est dans m’état q0 , s’il ne reste plus rien à lire
et que le sommet de la pile est A alors passer à l’état q1 et empiler le symbole B ;
– δ(q0 , a, A) = (q1 , A) signifie que si l’on est dans l’état q0 , si le symbole actuellement lu
est a et si le sommet de la pile est A alors passer à l’état q1 et ne rien faire avec la pile ;
– δ(q0 , a, A) = (q1 , ε) signifie que si l’on est dans l’état q0 , si le symbole actuellement lu
est a et si le sommet de la pile est A alors passer à l’état q1 et dépiler un symbole de la
pile.

Un mot w est accepté par un automate à pile si après avoir lu tout le mot w, l’automate se
trouve dans un état final. Le contenu de la pile importe peu du fait que l’on peut toujours la
vider (comment ?). Par conséquent, un mot est rejeté par un automate à pile :
– Si lorsque aucune transition n’est possible, l’automate n’a pas pu lire tout le mot ou bien
il se trouve dans un état non final.
– Si une opération incorrecte est menée sur la pile : dépiler alors que la pile est vide.

Exemple 23 : L’automate reconnaissant les mots an bn (avec n > 0) est le suivant : A =

({a, b}, {A, ⊲}, {q0 , q1 , q2 }, q0 , {q2 }, δ) tel que δ est définie par :
– δ(q0 , a, ⊲) = (q0 , A⊲)
– δ(q0 , a, A) = (q0 , AA)
– δ(q0 , b, A) = (q1 , ε)
– δ(q1 , b, A) = (q1 , ε)
– δ(q1 , ε, ⊲) = (q2 , ⊲)
– δ(q0 , ε, ⊲) = (q2 , ⊲)
Détaillons la reconnaissance de quelques mots :
1. Le mot aabb : (q0 , a, ⊲) →(q0 , a, A⊲) →(q0 , b, AA⊲) →(q1 , b, A⊲) →(q1 , ε, ⊲) →(q2 , ε, ⊲).
Le mot est reconnu ;
2. Le mot aab : (q0 , a, ⊲) →(q0 , a, A⊲) →(q0 , b, AA⊲) →(q1 , ε, A⊲). Le mot n’est pas re-
connu car il n’y a plus de transitions possibles alors que l’état de l’automate n’est pas
final
3. Le mot abb : (q0 , a, ⊲) →(q0 , b, A⊲) →(q1 , b, ⊲). Le mot n’est pas reconnu car on n’arrive
pas à lire tout le mot ;
4. Le mot ε : (q0 , ε, ⊲) →(q2 , ε, ⊲). Le mot est reconnu.

4.1.1 Les automates à piles et le déterminisme

Comme nous l’avons signalé dans le chapitre des automates à états finis, la notion du
déterminisme n’est pas propre à ceux-là. Elle est également présente dans le paradigme des
automates à piles. On peut donc définir un automate à pile déterministe par :

Définition 23 : Soit l’automate à pile défini par A = (X, Π, Q, q0 , F, δ). A est dit déterministe
si ∀qi ∈ Q, ∀a ∈ (X ∪ {ε}), ∀A ∈ Π, il existe au plus une paire (qj , B) ∈ (Q × Π∗ ) tel que
4.1. Les automates à piles 40

δ(qi , a, A) = (qj , B).

En d’autres termes, un automate à pile non déterministe possède plusieurs actions à en-
treprendre lorsqu’il se trouve dans une situation déterminée. La reconnaissance se fait donc
en testant toutes les possibilités jusqu’à trouver celle permettant de reconnaître le mot.

Exemple 24 : Considérons le langage suivant : wcwR tel que w ∈ (a|b)∗ . La construction

d’un automate à pile est facile, son idée consiste à empiler tous les symboles avant le c et de
les dépiler dans l’ordre après (l’état q2 est final) :
– δ(q0 , a, ⊲) = (q0 , A⊲)
– δ(q0 , b, ⊲) = (q0 , B⊲)
–
– δ(q0 , a, A) = (q0 , AA)
– δ(q0 , a, B) = (q0 , AB)
– δ(q0 , b, A) = (q0 , BA)
– δ(q0 , b, B) = (q0 , BB)
–
– δ(q0 , c, A) = (q1 , A)
– δ(q0 , c, B) = (q1 , B)
– δ(q0 , c, ⊲) = (q1 , ⊲)
–
– δ(q1 , a, A) = (q1 , ε)
– δ(q1 , b, B) = (q1 , ε)
– δ(q1 , ε, ⊲) = (q2 , ⊲ε)
Considérons maintenant le langage wwR tel que w ∈ (a|b)∗ , les mots de ce langage sont
palindromes mais on ne sait quand est-ce qu’il faut arrêter d’empiler et procéder au dépile-
ment. Il faut donc supposer que chaque symbole lu représente le dernier symbole de w, le
dépiler, continuer la reconnaissance si cela ne marche pas, il faut donc revenir empiler, et ainsi
de suite :
– δ(q0 , a, ⊲) = (q0 , A⊲)
– δ(q0 , b, ⊲) = (q0 , B⊲)
–
– δ(q0 , a, A) = (q0 , AA)
– δ(q0 , a, B) = (q0 , AB)
– δ(q0 , b, A) = (q0 , BA)
– δ(q0 , b, B) = (q0 , BB)
–
– δ(q0 , a, A) = (q1 , ε)
– δ(q0 , b, B) = (q1 , ε)
– δ(q0 , a, B) = (q1 , ε)
– δ(q0 , b, A) = (q1 , ε)
–
– δ(q1 , a, A) = (q1 , ε)
– δ(q1 , b, B) = (q1 , ε)
– δ(q1 , ε, ⊲) = (q2 , ⊲ε)

Malheureusement, nous ne pouvons pas transformer tout automate à piles non détermi-
niste en un automate déterministe. En effet, la classe des langages reconnus par des automates
4.2. Les grammaires hors-contextes 41

à piles non déterministes est beaucoup plus importantes que celle des langages reconnus par
des automates déterministes. Si LDET est l’ensemble des langages reconnus par des automates
à piles déterministes et LNDET est l’ensemble des langages reconnus par des automates à piles
non déterministes, alors :
LDET ⊂ LNDET
Nous allons à présent nous intéresser aux grammaires qui génèrent les langages algé-
briques puisque c’est la forme de ces grammaires qui nous permettra de construire des auto-
mates à pile.

4.2 Les grammaires hors-contextes

Nous avons déjà évoqué ce type de grammaires dans le premier chapitre lorsque nous
avons présenté la hiérarchie de Chomsky. Rappelons-le quand même :

Définition 24 : Soit G = (V, N, S, R) une grammaire quelconque. G est dite hors-contexte

ou de type de 2 si tous les règles de production sont de la forme : α → β tel que α ∈ N et
β ∈ (V + N)∗ .

Un langage généré par une grammaire hors-contexte est dit langage hors-contexte. Notons
que nous nous intéressons, en particulier, à ce type de langages (et par conséquence à ce type
de grammaires) du fait que la plupart des langages de programmation sont hors-contextes.
Ceci est dû au fait que le temps d’analyse des mots générés par certaines grammaires hors-
contextes est linéaire.

Exemple 25 : Soit la grammaire générant le langage an bn (n > 0) : G = ({a, b}, {S}, S, R) tel
que R comporte les règles : S → aSb|ε. D’après la définition, cette grammaire est hors-contexte
et le langage an bn est hors-contexte.

4.2.1 Arbre de dérivation

Vu la forme particulière des grammaires hors-contextes (présence d’un seul symbole non
terminal à gauche), il est possible de construire un arbre de dérivation pour un mot généré.

Définition 25 : Etant donnée une grammaire G = (V, N, S, R), les arbres de syntaxe de G sont
des arbres dont les noeuds internes sont étiquetés par des symboles de N, les feuilles étiquetés
par des symboles de V, tels que : si le nœud p apparaît dans l’arbre et si la règle p → a1 ...an
(ai terminal ou non terminal) est utilisée dans la dérivation, alors le nœud p possède n fils
correspondant aux symboles ai .
Si l’arbre syntaxique a comme racine S, alors il est dit arbre de dérivation du mot u tel que
u est le mot obtenu en prenant les feuilles de l’arbre dans le sens gauche→droite et bas→haut.

Exemple 26 : Reprenons l’exemple précédent, le mot aabb est généré par cette grammaire
par la chaîne : S → aSb → aaSbb → aaεbb = aabb. L’arbre de dérivation est donnée par la
figure 4.1.
4.2. Les grammaires hors-contextes 42

a S b

a S b

Figure 4.1 – Exemple d’un arbre de dérivation

4.2.2 Notion d’ambiguïté

Nous avons déjà évoqué la notion de l’ambiguïté lorsque nous avons présenté les expres-
sions régulières. Nous avons, alors, défini une expression régulière ambiguë comme étant une
expression régulière pouvant coller à un mot de plusieurs manière.
Par analogie, nous définissons la notion de l’ambiguïté des grammaires. Une grammaire
est dite ambiguë si elle peut générer au moins un mot de plus d’une manière. En d’autres
termes, si on peut trouver un mot généré par la grammaire et possédant au moins deux
arbres de dérivation, alors on dit que la grammaire est ambiguë. Notons que la notion de
l’ambiguïté n’a rien à avoir avec celle du non déterminisme. Par exemple, la grammaire G =
({a, b}, {S}, S, {S → aSb|bSa|ε}) génère les mots wwR tel que w ∈ (a|b)∗ . Bien qu’il n’existe
aucun automate à pile déterministe reconnaissant les mots de ce langage, tout mot ne possède
qu’un seul arbre de dérivation.
L’ambiguïté de certaines grammaires peut être levée comme le montre l’exemple suivant :

Exemple 27 : Soit la grammaire G = ({0, 1, +, ∗}, {E}, E, {E → E + E|E ∗ E|(E)|0|1}). Cette gram-
maire est ambiguë car le mot 1+1*0 possède deux arbres de dérivation (figures 4.2 et 4.3). La
grammaire est donc ambiguë. Or ceci pose un problème lors de l’évaluation de l’expression
(rappelons que l’évaluation se fait toujours de gauche à droite et bas en haut) 4 . Le premier
arbre évalue l’expression comme étant 1+(1*0) ce qui donne 1. Selon le deuxième arbre, l’ex-
pression est évaluée comme étant (1+1)*0 ce qui donne 0 ! Or, aucune information dans la
grammaire ne permet de préférer l’une ou l’autre forme.

E + E

1 E * E

1 0

Figure 4.2 – Un premier arbre de dérivation

4. Nous considérons le contexte de l’algèbre de Boole

4.3. Simplification des grammaires hors-contextes 43

E * E

E + E 0

1 1

Figure 4.3 – Deuxième arbre de dérivation

D’une manière générale, pour lever l’ambiguïté d’une grammaire, il n’y a pas de méthodes
qui fonctionne à tous les coups. Cependant, l’idée consiste généralement à introduire une
hypothèse supplémentaire (ce qui va changer la grammaire) en espérant que le langage généré
soit le même. Par exemple, la grammaire G ′ = ({+, ∗, 0, 1}, {E, T , F}, E, {E → E + T |T , T →
T ∗ F|F, F → (E)|0|1}) génère le même langage que G mais a l’avantage de ne pas être ambiguë.
La transformation introduite consiste à donner une priorité à l’opérateur * par rapport à
l’opérateur +.

4.2.3 Équivalence des grammaires hors-contextes et les automates à piles

Le théorème suivant établit l’équivalence entre les grammaires hors-contextes et les au-
tomates à piles. Néanmoins, ni le théorème ni sa preuve ne fournissent des moyens pour le
passage d’une forme à une autre.

Théorème 3 : Tout langage hors-contexte est un langage algébrique et vice-versa. En d’autres

termes, pour tout langage généré par une grammaire hors-contexte, il existe un automate à
pile (déterministe ou non) qui le reconnaît. Réciproquement, pour tout langage reconnu par
un automate à pile, il existe une grammaire hors-contexte qui le génère.

Dans le paradigme des langages algébriques, il est plus intéressant de s’intéresser aux
grammaires (rappelons qu’il n’existe pas d’expression régulière ici !). Ceci est dû à l’existence
de nombreux algorithmes et outils traitant plutôt des formes particulières de grammaires
(Chomsky, Greibach) cherchant ainsi à faciliter la construction des arbres de dérivation.

4.3 Simplification des grammaires hors-contextes

4.3.1 Les grammaires propres
Une grammaire hors-contexte (V, N, S, R) est dite propre si elle vérifie :
– ∀A → u ∈ R : u 6= ε ou A = S ;
– ∀A → u ∈ R : S ne figure pas dans u ;
– ∀A → u ∈ R : u ∈/ N;
– Tous les non terminaux sont utiles, c’est-à-dire qu’ils vérifient :
∗
– ∀A ∈ N : A est atteignable depuis S : ∃α, β ∈ (N + V)∗ : S → − αAβ ;
∗
– ∀A ∈ N : A est productif : ∃w ∈ V ∗ : A →
− w.
4.4. Les formes normales 44

Il est toujours possible de trouver une grammaire propre pour toute grammaire hors-
contexte. En effet, on procède comme suit :
1. Rajouter une nouvelle règle S ′ → S tel que S ′ est le nouvel axiome ;
2. Éliminer les règles A → ε :
∗
– Calculer l’ensemble E = {A ∈ N ∪ {S ′ }|A →
− ε} ;
– Pour tout A ∈ E, pour toute règle B → αAβ de R
– Rajouter la règle B → αβ
– Enlever les règles A → ε
∗
3. Eliminer les règles A −
→ B, on applique la procédure suivante sur R privée de S ′ → ε :
∗
– Calculer toutes les paires (A, B) tel que A →
− B
– Pour chaque paire (A, B) trouvée
– Pour chaque règle B → u1 |...|un rajouter la règle A → u1 |...|un
– Enlever toutes les règles A → B
4. Supprimer tous les non-terminaux non-productifs
5. Supprimer tous les non-terminaux non-atteignables.

4.4 Les formes normales

4.4.1 La forme normale de Chomsky
Soit G = (V, N, S, R) une grammaire hors-contexte. On dit que G est sous forme normale
de Chomsky si les règles de G sont toutes de l’une des formes suivantes :
– A → BC, A ∈ N, B, C ∈ N − {S}
– A → a, A ∈ N, a ∈ V
– S→ε
L’intérêt de la forme normale de Chomsky est que les arbres de dérivations sont des arbres
binaires ce qui facilite l’application de pas mal d’algorithmes.
Il est toujours possible de transformer n’importe quelle grammaire hors-contexte pour
qu’elle soit sous la forme normale de Chomsky. Notons d’abord que si la grammaire est
propre, alors cela facilitera énormément la procédure de transformation. Par conséquent, on
suppose ici que la grammaire a été rendue propre. Donc toutes les règles de S sont sous l’une
des formes suivantes :
– S→ε
– A → w, w ∈ V +
– A → w, w ∈ ((N − {S}) + V)∗
La deuxième forme peut être facilement transformée en A → BC. En effet, si

w = au, u ∈ V +

alors il suffit de remplacer la règle par les trois règles A → A1 A2 , A1 → a et A2 → u. Ensuite,

il faudra transformer la dernière règle de manière récursive tant que |u| > 1.
Il reste alors à transformer la troisième forme. Supposons que :

w = w1 A1 w2 A2 ...wn An wn+1 avec wi ∈ V ∗ et Ai ∈ (N − {S})

4.4. Les formes normales 45

La procédure de transformation est très simple. Si w1 6= ε alors il suffit de transformer cette

règle en :
A → B1 B2
B 1 → w1
B2 → A1 w2 A2 ...wn An wn+1
sinon, elle sera transformée en :
A → A1 B
B → w2 A2 ...wn An wn+1

Cette transformation est appliquée de manière récursive jusqu’à ce que toutes les règles soient
des règles normalisées.

Exemple 28 : Soit la grammaire dont les règles de production sont : S → aSbS|bSaS|ε, on

veut obtenir sa forme normalisée de Chomsky. On commence par la rendre propre, donc on
crée un nouvel axiome et on rajoute la règle S ′ → S puis on applique les transformations
citées plus haut. On obtient alors la grammaire suivante : S ′ → S, S → aSb|abS|bSa|baS. En
éliminant les formes A → B, on obtient alors la grammaire propre S ′ → aSb|abS|bSa|baS, S →
aSb|abS|bSa|baS. Nous allons à présent transformer juste les productions de S étant donné
qu’elles sont les mêmes que celles de S ′ .
– Transformation de S → aSb
– S → AU (finale)
– A → a (finale)
– U → Sb qui sera transformée en :
– U → SB (finale)
– B → b (finale)
– Transformation de S → abS
– S → AX (finale)
– X → bS qui sera transformée en :
– X → BS (finale)
– Transformation de S → bSa
– S → BY (finale)
– Y → Sa qui sera transformée en :
– Y → SA (finale)
– Transformation de S → baS
– S → BZ (finale)
– Z → aS qui sera transformée en :
– Z → AS (finale)

4.4.2 La forme normale de Greibach

Soit G = (V, N, S, R) une grammaire hors-contexte. On dit que G est sous la forme normale
de Greibach si toutes ses règles sont de l’une des formes suivantes :
– A → aA1 A2 ...An , a ∈ V, Ai ∈ N − {S}
– A → a, a ∈ V
– S→ε
L’intérêt pratique de la mise sous forme normale de Greibach est qu’à chaque dérivation, on
détermine un préfixe de plus en plus long formé uniquement de symboles terminaux. Cela
4.4. Les formes normales 46

permet de construire plus aisément des analyseurs permettant de retrouver l’arbre d’analyse
associé à un mot généré. Cependant, la transformation d’une grammaire hors-contexte en une
grammaire sous la forme normale de Greibach nécessite plus de travail et de raffinement de
la grammaire. Nous choisissons de ne pas l’aborder dans ce cours.