Université de Mostaganem

Faculté des Sciences Exactes et Informatique

Polycopié

Théorie des langages

Dr. Karim BESSAOUD

2017 - 2018
Table des matières

Introduction 6

1 Concepts de base 7
1.1 Langages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.1.1 Alphabet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.1.2 Mot . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.1.3 Définition formelle d’un langage . . . . . . . . . . . . . . . . . . 8
1.1.4 Opérations sur les langages . . . . . . . . . . . . . . . . . . . . . 9
[Link] Priorité des opérations sur les langages . . . . . . . . . 10
[Link] Quelques règles d’équivalence . . . . . . . . . . . . . . 11
1.2 Grammaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2.1 Définition formelle . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2.2 Les règles de production . . . . . . . . . . . . . . . . . . . . . . 12
1.2.3 Exemple de grammaire : . . . . . . . . . . . . . . . . . . . . . . 12
1.2.4 Types de grammaires . . . . . . . . . . . . . . . . . . . . . . . . 13
1.3 Automates ou reconnaisseurs . . . . . . . . . . . . . . . . . . . . . . . 13
1.3.1 Composition d’un automate . . . . . . . . . . . . . . . . . . . . 13
1.3.2 Définition formelle d’un automate . . . . . . . . . . . . . . . . . 14
1.3.3 Déterminisme des automates . . . . . . . . . . . . . . . . . . . 14
1.4 Classification de Chomsky . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.5 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2
 TABLE DES MATIÈRES

2 Langages réguliers 18
2.1 Langages réguliers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.1.1 Exemples de langages réguliers . . . . . . . . . . . . . . . . . . 18
2.1.2 Propriétés de fermeture des langages réguliers . . . . . . . . . . 18
2.2 Grammaires régulières . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2.1 Définition formelle . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2.2 Exemple de grammaire régulière . . . . . . . . . . . . . . . . . . 19
2.3 Automates à états finis . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.3.1 Composition d’un automate à états finis . . . . . . . . . . . . . 20
2.3.2 Définition formelle d’un automate à états finis . . . . . . . . . . 21
2.3.3 Procédure de reconnaissance dans les automates à états finis . . 21
2.3.4 Représentation des automates à états finis . . . . . . . . . . . . 22
[Link] Représentation formelle . . . . . . . . . . . . . . . . . 22
[Link] Représentation graphique . . . . . . . . . . . . . . . . 23
[Link] Représentation tabulaire . . . . . . . . . . . . . . . . . 24
2.3.5 Caractéristiques des automates à états finis . . . . . . . . . . . . 24
[Link] Automates à états finis complets / incomplets . . . . 24
[Link] Automates à états finis sans états inaccessibles / avec
des états inaccessibles . . . . . . . . . . . . . . . . . . 25
[Link] Automates à états finis déterministes / indéterministes 26
[Link] Automates minimaux / non minimaux . . . . . . . . . 29
2.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.5 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

3 Langages algébriques 35
3.1 Langages algébriques . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.1.1 Exemples de langages algébriques . . . . . . . . . . . . . . . . . 35
3.1.2 Propriétés de fermeture des langages algébriques . . . . . . . . . 35
3.2 Grammaires algébriques . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.2.1 Définition formelle . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.2.2 Exemple de grammaire algébrique . . . . . . . . . . . . . . . . . 36
3.3 Automates à pile . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.3.1 Composition d’un automate à pile . . . . . . . . . . . . . . . . . 37

3 [Link]
 TABLE DES MATIÈRES

3.3.2 Définition formelle d’un automate à pile . . . . . . . . . . . . . 37

3.3.3 Procédure de reconnaissance dans les automates à pile . . . . . 37
3.3.4 Représentation des automates à pile . . . . . . . . . . . . . . . . 38
3.3.5 Opérations sur la pile lors des transitions dans les automates à pile 38
3.3.6 Automates à pile indéterministes . . . . . . . . . . . . . . . . . 39
3.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.5 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

4 Langages contextuels 45
4.1 Langages contextuels . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.1.1 Exemples de langages contextuels . . . . . . . . . . . . . . . . . 45
4.1.2 Propriétés de fermeture des langages contextuels . . . . . . . . . 45
4.2 Grammaires de type 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.2.1 Définition formelle . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.2.2 Exemples de grammaires de type 1 . . . . . . . . . . . . . . . . 46
4.3 Machines de Turing à bornes linéaires . . . . . . . . . . . . . . . . . . . 48
4.3.1 Composition d’une Machine de Turing à bornes linéaires . . . . 48
4.3.2 Définition formelle d’une Machine de Turing à bornes linéaires . 49
4.3.3 Procédure de reconnaissance dans les machines de Turing à bornes
linéaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.3.4 Représentation des machines de Turing à bornes linéaires . . . . 50
4.3.5 Machines de Turing à bornes linéaires indéterministes . . . . . . 51
4.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.5 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

5 Langages récursivement énumérables et calculabilité 53

5.1 Langages récursivement énumérables . . . . . . . . . . . . . . . . . . . 53
5.1.1 Exemples de langages récursivement énumérables . . . . . . . . 53
5.1.2 Propriétés de fermeture des langages récursivement énumérables 53
5.2 Grammaires sans restriction . . . . . . . . . . . . . . . . . . . . . . . . 54
5.2.1 Définition formelle . . . . . . . . . . . . . . . . . . . . . . . . . 54
5.2.2 Exemple de grammaire sans restriction . . . . . . . . . . . . . . 54
5.3 Machines de Turing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
5.3.1 Composition d’une Machine de Turing . . . . . . . . . . . . . . 56

4 [Link]
 TABLE DES MATIÈRES

5.3.2 Définition formelle d’une Machine de Turing . . . . . . . . . . . 56

5.3.3 Représentation des Machines de Turing . . . . . . . . . . . . . . 57
5.3.4 Utilisations des Machines de Turing . . . . . . . . . . . . . . . . 57
5.3.5 Différence entre la reconnaissance avec les machines de Turing et
la reconnaissance avec les machines de Turing à bornes linéaires 57
5.4 Calculabilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
5.4.1 Procédure de calcul dans les Machines de Turing . . . . . . . . . 58
5.4.2 exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
5.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
5.6 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

6 Corrigés d’exercices 62

Corrigés d’exercices 62

Bibliographie 72

5 [Link]
Introduction

En linguistique et en informatique, on parle de théorie des langages pour décrire les

langages formels. Plus généralement, la théorie des langages concerne tout langage fini
ou infini qui peut être spécifié par une méthode ou un mécanisme fini, et explicite, qui
permet de le produire ou de l’analyser.
La théorie des langages ne se préoccupe pas du côté sémantique (le sens), mais plutôt
syntaxique (la forme) d’un langage. On définit un langage notamment grâce aux gram-
maires et on analyse les mots d’un langage grâce aux automates ou reconnaisseurs.
Ce cours va s’articuler autour de ces trois concepts que sont les langages, les grammaires
et les automates.
La théorie des langages est une base pour un certain nombre de disciplines informatique
dont principalement la compilation mais aussi, la logique, la complexité, la calculabi-
lité...
Nous allons étudier dans cette matière tous les types de langages décrits dans la clas-
sification de Chomsky que nous allons voir plus tard ainsi que les grammaires qui
permettent de les générer et les automates qui permettent de les reconnaı̂tre.
Dans le chapitre suivant, nous allons étudier les concepts de base des trois axes de
notre cours, à savoir les langages, les grammaires et les automates. Nous verrons aussi
la classification de Chomsky qui définit quatre grands types. Un chapitre sera par la
suite réservé à chaque type de langage.

6
Chapitre 1

Concepts de base

1.1 Langages

Un langage est tout système permettant de s’exprimer comme par exemple les langages
linguistiques, les langages mathématiques ou les langages informatiques.
La théorie des langages étudie les aspects purement syntaxiques de tels langages, c’est-
à-dire leurs structures internes formelles.
Un langage est constitué de mots qui sont eux-mêmes constitués de symboles faisant
partie d’un alphabet.

1.1.1 Alphabet

Un alphabet est un ensemble fini de symboles permettant de construire les mots d’un
langage.

Exemple :
— {0, 1}
— {if, then, else, x, y, z} dans cet exemple ‘if ’, ‘then’ et ‘else’ ne sont pas considérés
comme des mots mais bien comme des symboles.
— {+, −, ∗, /, =, a, b}

1.1.2 Mot

Un mot sur un alphabet est une séquence finie et ordonnée, éventuellement vide, de
symboles de l’alphabet. Le mot vide est noté ε.
Voici quelques exemples de mots :
— 100111 est un mot de l’alphabet {0, 1}.
— a = b est un mot de l’alphabet {+, −, ∗, /, =, a, b}.

7
 CHAPITRE 1. CONCEPTS DE BASE

La longueur d’un mot : La longueur d’un mot m est notée | m | et correspond au

nombre de symboles que contient ce mot.
On peut aussi avoir le nombre d’occurrence d’un symbole donnée par exemple | m |a
pour le nombre de a dans le mot m.

Exemple : Soit le mot m = 100111 sur l’alphabet {0, 1}.

| m |= 6.
| m |1 = 4.
| m |0 = 2.

1.1.3 Définition formelle d’un langage

Un langage, défini sur un alphabet A, est un ensemble de mots définis sur A. Un langage
peut être décrit de différentes manières :
— Un langage fini peut être décrit par l’énumération des mots qui le composent.
— Certains langages infinis peuvent être décrits par l’application d’opérations à des
langages plus simples. Ces opérations seront décrites en section 1.1.4.
— Certains langages infinis peuvent être décrits par un ensemble de règles appelé
grammaire.
— Enfin, certains langages infinis ne peuvent être décrits, ni par l’application d’opérations,
ni par un ensemble de règles. Dans ce type de langages, il n’existe pas d’algorithme
permettant de déterminer si un mot donné appartient à ce langage ou non.
Dans ce cours, nous allons nous intéresser uniquement aux langages qui peuvent être
décrits formellement et qui sont classés par la classification de Chomsky en quatre
types :

Type 3 : langages réguliers,

Type 2 : langages algébriques,
Type 1 : langages contextuels,
Type 0 : langages récursivement énumérables.

Il existe une relation d’inclusion entre ces quatre types de langages : type 3 ⊂ type 2 ⊂
type 1 ⊂ type 0 (voir figure 1.1). Par contre, on entend par langage de type i le premier
type en commençant par le type 3 qui vérifie les contraintes du type de langages. Un
langage de type 1 sous-entend implicitement qu’il n’est pas de type 2 et donc pas de
type 3.

8 [Link]
 CHAPITRE 1. CONCEPTS DE BASE

Figure 1.1: La relation d’inclusion entre les types de langages

1.1.4 Opérations sur les langages

Un langage étant un ensemble de mots (fini ou infini), les opérations définies sur les en-
sembles comme l’union, l’intersection ou encore le complément peuvent être appliquées
aux langages. Il existe aussi des opérations spécifiques telles que la concaténation,
l’image miroir ou l’étoile.

La concaténation : Soient deux mots u et v définis sur un alphabet A. La concaténation

de u avec v, notée u.v ou simplement uv, est le mot formé en faisant suivre les symboles
de u par les symboles de v.
Soient deux langages L1 et L2 définis sur un alphabet A. La concaténation de L1 avec
L2, notée L1L2, est le langage formé par les mots uv tel que u appartient à L1 et v
appartient à L2.
L1L2 = {m/m ∈ uv avec u ∈ L1 et v ∈ L2}

L’opération de puissance peut être appliquée à un alphabet,

L’étoile (la puissance) :
un langage, un mot ou un symbole.
On note a∗ , tel que a est un symbole, l’ensemble des mots constitués d’une suite de
symbole a d’une taille supérieure ou égale à 0.
On note a+ l’ensemble des mots constitués d’une suite de symbole a d’une taille
supérieure 0 donc sans le mot vide. a∗ = {ε} ∪ a+
On note A∗ l’ensemble des mots de longueur supérieure ou égale à 0 que l’on peut
construire à partir de l’alphabet A.
Soit un mot u ∈ A∗ et n un entier positif, on note un un mot constitué par la
concaténation de n fois u.

9 [Link]
 CHAPITRE 1. CONCEPTS DE BASE

Exemples : Soit un alphabet A = {a, b} on note :

— (ab)2 pour le mot abab
— ab2 pour le mot abb
— (a3 b)2 pour le mot aaabaaab
— a+ b∗ pour le langage infini qui est formé des mots constitué d’une suite non vide
de a suivie par une suite potentiellement vide de b.
— (a+ bc∗ )∗ ici, nous avons un langage à l’étoile. Le langage L = a+ bc∗ pour le langage
infini qui est formé des mots constitué d’une suite non vide de a suivie par un b
et d’une suite potentiellement vide de c. L∗ est constitué du mot vide, d’un mot
de L, et de la concaténation de plusieurs mots de L. ε, aabccc, abccaab sont des
exemples de mots appartenant à L∗ .

L’image miroir : L’image miroir d’un mot m notée mr est le mot m inversé. On a
donc : (mr )r = m. Par exemple l’image miroir du mot abb est le mot bba.
L’image miroir d’un langage L est le langage Lr qui est constitué des images inverse
des mots de L.
Lr est donc défini comme suit : Lr = {m/mr ∈ L}

L’union : L’union de deux langages L1 et L2 notée L1 ∪ L2 est l’ensemble des mots

qui appartiennent à au moins un des deux langages L1 et L2.
L1 ∪ L2 = {m/m ∈ L1 ou m ∈ L2}

L’intersection :L’intersection de deux langages L1 et L2 noté L1 ∩ L2 est l’ensemble

des mots qui appartiennent aux deux langages L1 et L2.
L1 ∩ L2 = {m/m ∈ L1 et m ∈ L2}

Le complément : Le complément d’un langage L1 est le langage C(L1) constitué de

l’ensemble des mots qui appartiennent à A∗ et pas à L1.
C(L1) = {m/m ∈ A∗ et m ∈
/ L1}

[Link] Priorité des opérations sur les langages

Comme vu précédemment, les langages peuvent être formés par des opérations telles
que l’union ou la concaténation.
Afin d’alléger l’écriture des langages, on introduit les priorités suivantes sur les opérations
les plus utilisées :
priorité(∗) > priorité(.) > priorité(∪)

Exemple : 0 ∪ 10∗ ⇔ (0 ∪ (1(0)∗ ))

10 [Link]
 CHAPITRE 1. CONCEPTS DE BASE

[Link] Quelques règles d’équivalence

Soient L1, L2 et L3, trois langages définis sur un alphabet A. Voici quelques règles
d’équivalence :
— L1 ∪ (L2 ∪ L3) = (L1 ∪ L2) ∪ L3
— L1 ∪ L2 = L2 ∪ L1
— L1 ∪ ∅ = L1
— L1 ∪ L1 = L1
— (L1 ∪ L2)L3 = L1L3 ∪ L2L3
— C(L1) ∪ L1 = A∗
— C(L1) ∩ L1 = ∅
— L1 ∩ ∅ = ∅
— ∅.L1 = L1.∅ = ∅
— ∅∗ = ε

1.2 Grammaires

Un langage peut être décrit par un certain nombre de règles. Pour les langages naturels,
le but étant de donner une description précise des règles permettant de construire des
phrases correctes d’une langue. Plus généralement, le but d’une grammaire est de donner
une description précise des règles permettant de construire tous les mots d’un langage.

Notation : Une grammaire G engendre un langage L(G) et un langage L est engendré

par une grammaire G(L).

Remarques : Une grammaire définit un seul langage. Par contre, un même langage
peut être engendré par plusieurs grammaires différentes.

1.2.1 Définition formelle

Une grammaire G est un quadruplet G = (T, N, S, R) telle que :

T est l’ensemble du vocabulaire terminal : c’est-à-dire l’alphabet sur lequel est
défini le langage (A).
N est l’ensemble du vocabulaire non terminal : c’est-à-dire l’ensemble des sym-
boles qui n’apparaissent pas dans les mots générés, mais qui sont utilisés au cours
de la génération.
S ∈ N est le symbole de départ ou axiome : c’est à partir de ce symbole non
terminal que l’on commencera la génération de mots au moyen des règles de la
grammaire.
R est l’ensemble des règles de production : ces règles permettent de générer
les mots d’un langage.

11 [Link]
 CHAPITRE 1. CONCEPTS DE BASE

1.2.2 Les règles de production

Les règles de production d’une grammaire sont de la forme :

u → v, avec u ∈ (N ∪ T )+ et v ∈ (N ∪ T )∗

Dans les règles de production on ne peut pas avoir le mot vide qui génère un mot v car
la partie gauche de la règle appartient à (N ∪ T )+ .
On peut avoir des règles du type : u → v/w pour u → v , u → w.
Lorsqu’on a une règle du type u → v, on dit que v dérive directement de u.
Lorsqu’on a u → u1 → u2 → u3. . . → u4 → v : on dit que v dérive de u et on le note
∗
u → v.
∗
Le langage L généré par une grammaire G est noté L(G) = {m/m ∈ T ∗ et S → m}.
Cela veut dire que L(G) est formé par tous les mots (formés par l’alphabet terminal)
qui peuvent être dérivés à partir de l’axiome.

1.2.3 Exemple de grammaire :

Soit une grammaire G = (T, N, S, R) telle que :

T = {a, b}
N = {S, S 0 }
R={
S → aS/bS 0 /ε
S 0 → bS 0 /ε
}
Exemple de mots générés par cette grammaire :
— ε : A partir de l’axiome S, on applique la règle qui donne le mot vide S → ε
— a : A partir de l’axiome S, on applique d’abord la règle S → aS puis la règle
S → ε. On a donc S → aS → a.
— b : A partir de l’axiome S, on applique d’abord la règle S → bS 0 puis la règle
S 0 → ε. On a donc S → bS 0 → b.
— aa, aaa, aa. . . .a, bb, bbb, bb. . . .b, ab, aab, abb, a..ab..b,. . .
Exemple de mots non générés par cette grammaire :
— ba : ce mot commence par un b, on applique donc d’abord la règle S → bS 0 .
Ensuite on a un a mais aucune règle ne permet d’avoir un a à partir de S 0 . Donc,
le mot ba ne peut pas être généré par cette grammaire.
— aba : ce mot commence par un a, on applique donc d’abord la règle S → aS.
Ensuite, on a un b, on applique alors la règle S → bS 0 . Ensuite, on a un a mais
aucune règle ne permet d’avoir un a à partir de S 0 . Donc, le mot aba ne peut pas
être généré par cette grammaire.
Le langage généré par cette grammaire est : a∗ b∗ .

12 [Link]
 CHAPITRE 1. CONCEPTS DE BASE

1.2.4 Types de grammaires

En introduisant des critères sur la forme des règles des grammaires, on obtient des
classes de grammaires hiérarchisées, ordonnées par inclusion. La classification de Chom-
sky, distingue quatre classes de grammaires :
Type 3 : grammaires régulières génèrent des langages réguliers,
Type 2 : grammaires algébriques génèrent des langages algébriques,
Type 1 : grammaire contextuelles génèrent des langages contextuels,
Type 0 : grammaire sans restriction génèrent des langages récursivement énumérables.

1.3 Automates ou reconnaisseurs

Un automate est une machine qui permet de lire un mot m et de dire formellement si m
appartient à un langage donné ou non. Un automate est un reconnaisseur qui permet
de reconnaitre tous les mots d’un langage L et uniquement les mots du langage L.

1.3.1 Composition d’un automate

Il existe plusieurs types d’automates. Ils ont presque tous une structure commune, mais
chacun à sa particularité. Un automate peut être composé de :
Une bande de lecture/écriture : Une bande est une succession de cases. C’est
dans les cases de cette bande qu’est écrit le mot à reconnaı̂tre. Chaque case
pouvant contenir un seul symbole de l’alphabet d’entrée (ou l’alphabet auxiliaire
d’écriture, si l’écriture est autorisé sur la bande).
Une tête de lecture/écriture : Une tête de lecture peut lire une case (ou écrire
dans une case) à un instant donné. La case sur laquelle se trouve la tête de lecture
à un moment donné s’appelle la case courante. La tête peut être déplacée par
l’automate pour se positionner sur la case immédiatement à gauche ou à droite
de la case courante.
Une mémoire : La mémoire n’est pas toujours présente dans un automate. La
mémoire possède un alphabet spécial. Elle est caractérisée par des fonctions
d’accès aux éléments et des fonctions de stockage.
Une unité de contrôle : L’unité de contrôle constitue le cœur d’un automate. Elle
peut être vue comme un programme qui dicte à l’automate son comportement.
Elle est définie par un ensemble fini d’états ainsi que par une fonction de transition
qui décrit le passage d’un état à un autre en fonction du contenu de la case
courante de la bande de lecture et du contenu de la mémoire. L’unité de contrôle
décide aussi de la direction dans laquelle il faut déplacer la tête de lecture et
choisit quels symboles stocker dans la mémoire.

13 [Link]
 CHAPITRE 1. CONCEPTS DE BASE

1.3.2 Définition formelle d’un automate

Un automate est défini au minimum par les éléments suivants :

A est l’alphabet des mots en entrée : c’est l’alphabet du langage des mots à
reconnaitre.
Q est un ensemble non vide d’états : l’automate utilise les états pour déterminer
à quel étape il se trouve dans la reconnaissance des mots.
I ⊆ Q est un ensemble non vide d’états initiaux : dans la plupart des auto-
mates, on a un seul état initial par lequel l’automate commence la reconnais-
sance. Il peut y avoir des automates qui possèdent plusieurs états initiaux. Ces
automates sont indéterministes (nous définirons dans la section suivante la notion
d’indéterminisme).
F ⊆ Q est un ensemble d’états finaux : ces états sont utilisés pour décider de
l’appartenance ou non d’un mot au langage.
δ est un ensemble de transitions : les transitions permettent de faire certaines
actions à la lecture d’un symbole, comme par exemple le changement d’état,
l’écriture, le stockage . . .

1.3.3 Déterminisme des automates

Un automate est un reconnaisseur des mots d’un langage donné L. L’objectif de l’auto-
mate est de lire un mot en entrée et de dire formellement si ce mot appartient ou non à
L. Nous avons une tête de lecture qui examine successivement chaque symbole du mot,
et selon la valeur du symbole déclenche la transition appropriée. Si à la fin, l’automate
se trouve dans une configuration considérée comme final, le mot appartient à L sinon,
quel que soit la configuration autre dans laquelle il se trouve, le mot n’appartient pas
à L. Par contre l’automate peut être confronté à deux types de problème :
1. Si l’automate possède plusieurs états initiaux, par quel état initial va-t-il com-
mencer la lecture ? Il doit alors essayer tous les états initiaux ; ce qui va générer
plusieurs chemins, et s’il y a au moins un chemin qui se termine dans une confi-
guration considérée comme final, cela veut dire que le mot appartient à L.
2. Si à un moment donné, à la lecture d’un symbole, plusieurs transitions sont pos-
sibles. Comment alors savoir quelle transition prendre ? Il faut alors essayer toutes
les transitions possibles ce qui va générer plusieurs chemins, et s’il y a au moins
un chemin qui se termine dans une configuration considérée comme final, cela
veut dire que le mot appartient à L.
Dans les deux cas cité ci-dessus, on se trouve devant un automate indéterministe. Par
opposition, on dit qu’un automate est déterministe si à tout instant de la lecture d’un
symbole du mot, il existe un seul choix possible.

14 [Link]
 CHAPITRE 1. CONCEPTS DE BASE

1.4 Classification de Chomsky

Il y a une forte relation entre les langages, les grammaires et les automates. Cette
relation est résumée dans le tableau 1.1 qui représente la classification de Chomsky.

Type du Langages Langages Grammaires Automates

Type 3 Langages réguliers Grammaires Automates à états
régulières finis
Type 2 Langages algébriques Grammaires Automates à pile
algébriques
Type 1 Langages contextuels Grammaires Machines de Turing
contextuelles à bornes linéaires
Type 0 Langages récursivement Grammaires Machines de Turing
énumérables sans restriction

Table 1.1: Classification de Chomsky

Dans les quatre chapitres suivants, nous détaillerons chaque type de langage, avec le
type de grammaire qui permet de générer les mot du langage et le type d’automate qui
permet la reconnaissance des mots du langage.

15 [Link]
 CHAPITRE 1. CONCEPTS DE BASE

1.5 Exercices

Exercice 1 : Soit l’alphabet A = {0, 1}

1. Étant donnés les mots u = 11 et v = 100, écrire les mots uv, u3 , u2 v 2 et (uv)2 .
2. Soit E1 l’ensemble de tous les mots m définis sur A tel que | m |= 3. Que vaut
E1 ?
3. Soit E2 l’ensemble de tous les mots m définis sur A tel que | m |< 5 et | m | mod
2 = 0. Que vaut E2 ?
4. Soit le langage L = 1+ 0∗ ∪ 0∗ 1∗ . Soit E3 l’ensemble de tous les mots m tel que
m ∈ L et | m |= 3. Que vaut E3 ?
5. Soit les langages L1 = 01+ et L2 = 10+ . Définir et essayer de simplifier les
langages L1L2, (L2)∗ L1 et L1 ∪ C(L1 ∩ L2).

Exercice 2 : Soit l’alphabet A = {a, b, c}.

1. Donner L1 le langage des mots définis sur A qui commencent par un a.
2. Donner L2 le langage des mots définis sur A qui se terminent par un a.
3. Donner L3 le langage des mots définis sur A qui contiennent au moins un a.
4. Donner L4 le langage des mots définis sur A qui contiennent au moins deux fois
la séquence aab.
5. Donner L5 le langage des mots définis sur A qui ne commencent pas par un a.

Exercice 3 :
1. Comment représenter le langage régulier constitué d’aucun mot ?
a) ε
b) {ε}
c) ∅
d) {∅}
2. Soit l’alphabet A = {a, b}, parmi ces langages, lequel représente le langage des
mots qui commence par un b.
a) (ba∗ )∗
b) b(a∗ b∗ )∗
c) (ba∗ )+
d) (ba∗ b∗ )+
3. Quels sont les équivalences correctes
a) (ab)∗ a = a(ba)∗
b) (a∗ b∗ )∗ = (a ∪ b)∗
c) (ab∗ )∗ = a(a∗ b∗ )∗
d) a∗ ∪ ε = a+

16 [Link]
 CHAPITRE 1. CONCEPTS DE BASE

4. Quel est la relation correct dans les langages ?

a) Type 3 ∈ Type 2
b) Type 2 ∈ Type 3
c) Type 3 ⊂ Type 2
d) Type 2 ⊂ Type 3

Exercice 4 : Remplir la grille de la figure 1.2 en respectant les langages des lignes et
des colonnes. Chaque ligne contient un mot du langage décrit pour cette ligne et la
même chose pour les colonnes. Chaque case contient un seul symbole. Les mots doivent
donc être de longueurs 10 ou 9 (Pour la dernière ligne et la dernière colonne).

Figure 1.2: Grille

17 [Link]
Chapitre 2

Langages réguliers

Dans ce chapitre, nous allons étudier les langages de type 3 appelés aussi langages
réguliers. Nous allons voir comment sont constitués ces langages, quelles sont les spécificités
des grammaires qui permettent de générer les langages réguliers et quels sont les auto-
mates qui permettent de reconnaitre les mots qui appartiennent à un langage régulier.

2.1 Langages réguliers

Un langage est régulier, si et seulement si, il existe une grammaire régulière générant
ce langage.

2.1.1 Exemples de langages réguliers

Étant donné un alphabet A,

— ∅(l’ensemble vide) est un langage régulier sur A.
— {ε} est un langage régulier sur A.
— {a} est un langage régulier sur A pour tout a ∈ A.
— Tout langage fini est régulier.
— L’ensemble de tous les mots A∗ est régulier.
— a∗ b∗ est régulier.

2.1.2 Propriétés de fermeture des langages réguliers

Si L1 et L2 sont des langages réguliers sur un alphabet A, alors les langages suivants
sont des langages réguliers :
— L1 ∪ L2 (L’union)
— L1L2 (La concaténation)
— L1∗ (L’étoile)
— L1 ∩ L2 (L’intersection)
— C(L1) (Le complément)

18
 CHAPITRE 2. LANGAGES RÉGULIERS

2.2 Grammaires régulières

Les grammaires régulières permettent de générer des langages réguliers.

2.2.1 Définition formelle

Il existe deux types de grammaires régulières équivalentes :

Grammaire régulière à droite : Une grammaire G = (T, N, S, R) est régulière à
droite si les règles de R sont de la forme :
S → aS 0 ou S → a ou S → ε. ∀(S, S 0 ) ∈ N et ∀a ∈ T
Grammaire régulière à gauche : Une grammaire G = (T, N, S, R) est régulière
à gauche si les règles de R sont de la forme :
S → S 0 a ou S → a ou S → ε. ∀(S, S 0 ) ∈ N et ∀a ∈ T

Remarque : Dans une grammaire régulière G = (T, N, S, R), on ne peut pas avoir une
règle où le symbole non terminal se trouve à gauche du symbole terminal et une autre
règle où le symbole non terminal se trouve à droite du symbole terminal comme par
exemple : S → aS/Sb.

2.2.2 Exemple de grammaire régulière

Soit un langage L = a∗ b∗ défini sur l’alphabet A = {a, b}.

Grammaire régulière à droite : Gd (L) est une grammaire régulière à droite :

Gd (L) = (T, Nd , Sd , Rd )
T = {a, b}
Nd = {Sd , Sd0 }
Rd = {
Sd → aSd /bSd0 /ε,
Sd0 → bSd0 /ε
}
Exemple de mot appartenant au langage L = a∗ b∗ : aab
Pour générer ce mot à partir de Gd (L) on applique d’abord la règle Sd → aSd pour
générer le premier a. Pour générer le deuxième a, on applique la même règle Sd → aSd .
Ensuite, on a un b, on applique alors la règle Sd → bSd0 . Pour finir, on applique la règle
Sd0 → ε. On a donc Sd → aSd → aaSd → aabSd0 → aab
Exemple de mot n’appartenant pas au langage L = a∗ b∗ : ba
Ce mot commence par un b, on applique d’abord la règle Sd → bSd0 pour générer le
premier b. Ensuite on a un a mais aucune règle ne permet de générer un a à partir de
Sd0 . Donc, le mot ba ne peut pas être généré par cette grammaire.

19 [Link]
 CHAPITRE 2. LANGAGES RÉGULIERS

Grammaire régulière à gauche : Gg (L) est une grammaire régulière à gauche :

Gg (L) = (T, Ng , Sg , Rg )
T = {a, b}
Ng = {Sg , Sg0 }
Rg = {
Sg → Sg b/Sg0 a/ε,
Sg0 → Sg0 a/ε
}
Exemple de mot appartenant au langage L = a∗ b∗ : aab
Ce mot se termine par un b, on applique d’abord la règle Sg → Sg b. Ensuite, on a un
a, on applique alors la règle Sg → Sg0 a. Ensuite, on a un autre a, on applique alors la
règle Sg0 → Sg0 a. Le mot est formé après application de la règle Sg0 → ε. On a donc
Sg → Sg b → Sg0 ab → Sg0 aab → aab
Exemple de mot n’appartenant pas au langage L = a∗ b∗ : ba
ce mot se termine par un a, on applique d’abord la règle Sg → Sg0 a. Ensuite on a un b
mais aucune règle ne permet de générer un b à partir de Sg0 . Donc, le mot ba ne peut
pas être généré par cette grammaire.

Remarque : On voit bien à travers cet exemple la différence entre une grammaire
régulière à droite et une grammaire régulière à gauche. Le principe dans la grammaire
régulière à droite est de faire la génération des mots du langage du début vers la fin,
contrairement à la grammaire régulière à gauche où le raisonnement est inverse : la
génération se fait de la fin vers le début des mots.

2.3 Automates à états finis

Un automate est une machine qui permet de lire un mot m et de dire formellement si
m appartient à un langage donné.
Un automate est un reconnaisseur qui permet de reconnaı̂tre tous les mots d’un langage
donné.
Les automates qui permettent de reconnaitre les langages réguliers sont les automates
à états finis.

Remarque : Pour un langage régulier L, on peut avoir plusieurs automates à états

finis qui reconnaissent les mots de L. Par contre, un automate à états finis ne peut
reconnaitre les mots que d’un seul langage.

2.3.1 Composition d’un automate à états finis

Un automate à états finis est composé de :

20 [Link]
 CHAPITRE 2. LANGAGES RÉGULIERS

Une bande de lecture : La bande est composée d’une succession de cases. C’est
dans les cases de cette bande qu’est écrit le mot à reconnaı̂tre. Chaque case
pouvant contenir un seul symbole de l’alphabet d’entrée.
Une tête de lecture : La tête de lecture lit à un instant donné la case courante
avant de se déplacer sur la case suivante. La case courante est la case sur laquelle
est positionnée la tête de lecture. La tête de lecture est initialement positionnée
sur le premier symbole du mot et se déplace toujours d’une seule case à la fois
vers la droite.
Une unité de contrôle : L’unité de contrôle constitue le cœur d’un automate. Elle
peut être vue comme un programme qui dicte à l’automate son comportement.
Elle est définie par un ensemble fini d’états ainsi que par une fonction de transition
qui décrit le passage d’un état à un autre en fonction du contenu de la case
courante et de l’état courant. A chaque fois qu’une transition s’exécute, la tête
de lecture se déplace d’une seule case vers la droite.

2.3.2 Définition formelle d’un automate à états finis

Un automate à états finis AEF est un quintuplet AEF = (A, Q, I, F, δ) :

A est l’alphabet des mots en entrée : c’est l’alphabet du langage des mots à
reconnaitre.
Q est un ensemble non vide d’états : l’automate à états finis utilise les états
pour déterminer à quel étape il se trouve dans la reconnaissance des mots.
I ⊆ Q est un ensemble non vide d’états initiaux : dans la plupart des auto-
mates à états finis, il n’y a qu’un seul état initial par lequel l’automate à états
finis commence la reconnaissance. Il peut y avoir des automates à états finis qui
possèdent plusieurs états initiaux. Ces automates à états finis sont des automates
à états finis indéterministes.
F ⊆ Q est un ensemble d’états finaux : l’ensemble des états finaux est utilisé
pour la reconnaissance des mots. Si la reconnaissance se termine dans un état
final, le mot est reconnu comme appartenant au langage. Sinon, le mot n’est pas
reconnu par l’automate à états finis comme appartenant au langage.
δ est un ensemble de transitions : les transitions permettent de faire les chan-
gements d’états à la lecture d’un symbole.

2.3.3 Procédure de reconnaissance dans les automates à états finis

La reconnaissance des mots par l’automate à états finis commence par un état initial.
A chaque symbole lu, l’automate à états finis peut changer l’état dans lequel il se trouve
et la tête de lecture se déplace d’une case à droite.
Un mot est reconnu par un automate à états finis si est seulement si à la fin de la lecture
du mot, l’automate à états finis se trouve dans un état final.

21 [Link]
 CHAPITRE 2. LANGAGES RÉGULIERS

2.3.4 Représentation des automates à états finis

Nous allons voir dans ce qui suit trois façons de représenter les automates à états finis :
— Représentation formelle
— Représentation graphique
— Représentation tabulaire
Ces trois types de représentation sont équivalentes, elles contiennent exactement les
mêmes informations.

[Link] Représentation formelle

Un automate à états finis AEF peut être représenté d’une façon formelle en définissant
tous les ensembles qui définissent un automate à états finis AEF = (A, Q, I, F, δ).
Les transitions sont écrites sous la forme suivante : (état source, symbole lu) → (état
destination)

Exemple : Soit un langage L = a∗ b∗ défini sur l’alphabet A = {a, b}. Nous allons
donner une représentation formelle de l’automate à états finis AEF (L).
AEF (L) = {A, Q, I, F, δ)
A = {a, b}
Q = {e0 , e1 }
I = {e0 }
F = {e0 , e1 }
δ={
(e0 , a) → (e0 ),
(e0 , b) → (e1 ),
(e1 , b) → (e1 )
}
Exemple de mot appartenant au langage L = a∗ b∗ : aab
Au début, l’automate se trouve à l’état initial e0 (il y a un seul état initial) et la tête
de lecture sur le premier symbole du mot à savoir a. Il existe une transition qui va de
cette configuration vers l’état e0 ((e0 , a) → (e0 )). La tête de lecture se situe alors sur
le deuxième symbole du mot à savoir un a, et l’automate est resté dans l’état e0 . Il va
alors faire la même chose que pour le premier symbole à savoir (e0 , a) → (e0 ). La tête
de lecture se situe alors sur le troisième symbole du mot à savoir un b, et l’automate
est resté dans l’état e0 . Il existe une transition qui va de cette configuration vers l’état
e1 ((e0 , b) → (e1 )). Le mot est terminé et l’automate se trouve dans l’état e1 qui est un
état final, le mot est alors reconnu par l’automate.
Exemple de mot n’appartenant pas au langage L = a∗ b∗ : ba
Au début, l’automate se trouve à l’état initial e0 et la tête de lecture sur le premier
symbole du mot à savoir b. Il existe une transition qui va de cette configuration vers

22 [Link]
 CHAPITRE 2. LANGAGES RÉGULIERS

l’état e1 ((e0 , b) → (e1 )). La tête de lecture se situe alors sur le deuxième symbole
du mot à savoir un a, et l’automate est à l’état e1 . A partir de cette configuration, il
n’existe pas de transition possible. Donc ce mot n’est pas reconnu par l’automate.

[Link] Représentation graphique

Un automate à états finis peut être représenté par un graphe dans lequel :

— Les nœuds du graphe sont les états

— Les arcs sont les transitions possibles avec la fonction de transition
— La pondération de chaque arc est le symbole ou les symboles (séparé par des
virgules) qui peuvent être lus lors du changement d’état de ei à ej . Le passage

d’un état à un autre se fait avec la lecture d’un seul symbole.

— Les états initiaux sont identifiés par une flèche entrante.

— Les états finaux sont identifiés par un double cercle.

Exemple : Soit un langage L = a∗ b∗ défini sur l’alphabet A = {a, b}. Nous donnons
dans la figure 2.1 une représentation graphique de l’automate à états finis AEF (L).

Figure 2.1: AEF(L)

Exemple de mot appartenant au langage L = a∗ b∗ : aab

Au début, l’automate se trouve à l’état initial e0 (l’état initial identifié par une flèche
entrante) et la tête de lecture sur le premier symbole du mot à savoir a. Il existe une
transition qui va de cette configuration vers l’état e0 (il existe une boucle dans e0 avec
le symbole a). La tête de lecture se situe alors sur le deuxième symbole du mot à savoir
un a, et l’automate reste à l’état e0 . Il boucle à nouveau sur e0 avec le a. La tête de
lecture se situe alors sur le troisième symbole du mot à savoir un b, et l’automate reste
à l’état e0 . Il existe une transition qui va de cette configuration vers l’état e1 (il existe
un arc pondéré par un b qui va de e0 vers e1 ). Le mot est terminé et l’automate se
trouve à l’état e1 qui est un état final (identifié par un double cercle), le mot est alors
reconnu par l’automate.

23 [Link]
 CHAPITRE 2. LANGAGES RÉGULIERS

Exemple de mot n’appartenant pas au langage L = a∗ b∗ : ba

Au début, l’automate se trouve à l’état initial e0 et la tête de lecture sur le premier
symbole du mot à savoir b. Il existe une transition qui va de cette configuration vers
l’état e1 (il existe un arc pondéré par un b qui va de e0 vers e1 ). La tête de lecture se
situe alors sur le deuxième symbole du mot à savoir un a, et l’automate est à l’état e1 .
A partir de cette configuration, il n’existe pas de transition possible (il n’existe aucun
arc sortant de e1 avec le symbole a). Donc ce mot n’est pas reconnu par l’automate.

[Link] Représentation tabulaire

La représentation tabulaire s’appuie sur une matrice où chaque ligne représente un état
source, chaque colonne représente un symbole de l’alphabet et chaque case de la matrice
représente le ou les états destinations des transitions.
Les états initiaux sont marqués par des flèches entrantes et les états finaux par des
flèches sortantes.

Exemple : Soit un langage L = a∗ b∗ défini sur l’alphabet A = {a, b}. Nous donnons
dans la table 2.1 une représentation tabulaire de l’automate à états finis AEF (L).

a b
→
← e0 e0 e1
← e1 e1

Table 2.1: AEF(L)

Vous pouvez vous exercer à faire le déroulement d’exemples de mots qui appartiennent
et de mots qui n’appartiennent pas au langage L.

2.3.5 Caractéristiques des automates à états finis

[Link] Automates à états finis complets / incomplets

Un automate est complet si sa fonction de transition δ est définie pour tout état de
l’automate et tout symbole de l’alphabet.
Pour tout automate à états finis incomplet, il existe un automate à états finis complet
équivalent.
Pour rendre un automate à états finis complet, il peut être nécessaire de rajouter un état
supplémentaire appelé état puits (ep ), vers lequel vont toutes les transitions impossibles.
L’état puits n’est évidemment pas un état final. Donc, si la reconnaissance d’un mot se
termine dans un état puits, on peut conclure que ce mot ne fait pas partie du langage.

24 [Link]
 CHAPITRE 2. LANGAGES RÉGULIERS

Exemples : Soit un langage L = a∗ b∗ défini sur l’alphabet A = {a, b}. Nous allons
donner une représentation graphique de l’automate à états finis complet de L (figure
2.2).

Figure 2.2: AEF(L)

Pour faire l’automate complet de L, il a été nécessaire de rajouter un nouvel état (ep ).
Soit un langage L0 = (a∗ b∗ )∗ défini sur l’alphabet A = {a, b}. Nous allons donner une
représentation graphique de l’automate à états finis complet de L0 (figure 2.3).

Figure 2.3: AEF(L’)

Contrairement à l’automate de L, l’automate de L0 est déjà complet sans l’ajout d’un

état puits.

[Link] Automates à états finis sans états inaccessibles / avec des états inaccessibles

Un automate à états finis est un automate sans états inaccessibles si tous les états
de l’automate sont accessibles à partir de l’ensemble des états initiaux. Un état ei
est accessible à partir de l’ensemble des états initiaux s’il existe au moins un chemin
menant d’un état initial vers l’état ei dans le graphe de l’automate. Plus formellement,
cela implique qu’il existe une suite de transitions menant d’un état initial vers l’état ei .
Pour tout automate à états finis avec des états inaccessibles, il existe un automate à
états finis sans états inaccessibles équivalent.
Pour passer d’un automate avec des états inaccessibles à un automate sans états in-
accessibles, il suffit de supprimer tous les états inaccessibles ainsi que les transitions
entrantes et sortantes de ces états.

25 [Link]
 CHAPITRE 2. LANGAGES RÉGULIERS

Exemple : Soit l’automate à états finis de la figure 2.4 :

Dans l’exemple, l’état e0 est un état initial et donc forcément e0 est un état accessible.
e1 est accessible à partir de e0 avec un b. Par contre, e3 et e4 ne sont pas accessibles à
partir de e0 .

Figure 2.4: AEF avec des états inaccessibles

Pour passer à l’automate à états finis sans états inaccessibles, il suffit de supprimer les
états e3 et e4 . On retrouve l’automate à états finis de la figure 2.1 reconnaissant les
mots du langage L = a∗ b∗ .

[Link] Automates à états finis déterministes / indéterministes

Un automate à états finis est dit indéterministe si au moins une des conditions suivantes
est vraie :
— Il a plusieurs états initiaux.
— Étant donné un état ei ∈ Q et un symbole a ∈ A, il existe plusieurs transitions
possibles.
Lorsqu’on a un automate à états finis indéterministe, pour savoir si un mot appartient
au langage reconnu par l’automate, il est nécessaire de prendre tous les chemins possibles
dans l’automate à chaque fois qu’il y en a plusieurs, et s’il y a au moins un chemin qui
finit dans un état final, alors le mot est reconnu par l’automate à états finis comme
faisant parti du langage. Le temps de calcul peut rapidement augmenter surtout si
l’automate à états finis est grand avec des choix multiples dans plusieurs états.
Pour tout automate à états finis indéterministe, il existe un automate à états finis
déterministe équivalent.
Il existe un algorithme (Algorithme 1) qui permet de transformer un automate à
états finis indéterministe (AEF I) en un automate à états finis déterministe (AEF D)
équivalent.
Pour dérouler cet algorithme, il est conseillé d’utiliser la représentation tabulaire qui
permet de réduire le risque d’erreurs.

26 [Link]
 CHAPITRE 2. LANGAGES RÉGULIERS

Algorithme 1 : rendDéterministe
Entrée : AEF I = (A, Q, I, F, δ)
Sortie : AEF D = (A, Qd , e0d , Fd , δd ) {tel que L(AEF I) = L(AEF D) }
e0d ← I ; {e0d est un état qui regroupe tous les états initiaux de AEF I}
Qd ← e0d ; {initialement Qd contient l’état initial e0d }
vus ← ∅ ; {vus est l’ensemble des états de Qd qui ont été traités. Initialement, aucun
état n’est traité}
δd ← ∅ ; {initialisation de δd }
Tant que Qd 6= vus faire
soit eid ∈ Qd et eid ∈/ vus ; {prendre un état de Qd pas encore traité}
Pour tout a ∈ A faire
ekd ← {ek /∃ei ∈ eid , (ei , a) → (ek ) ∈ δ} ; {ekd est l’état formé par l’ensemble des
états ek qui sont les destinataires des transitions sortants avec le symbole a des
états ei formant eid }
Qd ← Qd ∪ {ekd } ; {ekd est ajouté à Qd s’il n’existe pas déjà}
δd ← δd ∪ {(eid , a) → (ekd )} ; {une nouvelle transition est ajoutée à δd }
Fin Pour
vus ← vus ∪ {eid } ; {ajouter eid à l’ensemble des états traités}
Fin Tant que
Fd ← {eid ∈ Qd /eid ∩ F 6= ∅} ; {l’ensemble des états finaux est composé des états qui
contiennent au moins un état final de F }

Exemple : Soit l’automate à états finis indéterministe ci-dessous reconnaissant les mots
du langage L = a+ c+ ∪ b+ c+ .

Figure 2.5: AEFI du langage L = a+ c+ ∪ b+ c+

Ci-dessous, la représentation tabulaire de cet automate AEF I qui permet de faciliter

le déroulement de l’algorithme 1.

On a deux états initiaux (deux flèches entrantes dans la représentation tabulaire) et

avec le même symbole et à partir d’un même état, on peut aller vers plusieurs états (des
cases qui contiennent deux états dans la représentation tabulaire). Il suffisait qu’une des

27 [Link]
 CHAPITRE 2. LANGAGES RÉGULIERS

a b c
→ e0 {e0 , e1 }
e1 {e1 , e2 }
← e2
→ e3 {e1 , e3 }

Table 2.2: La représentation tabulaire de l’AEFI du langage L = a+ c+ ∪ b+ c+

deux conditions soit vérifiée pour que l’automate soit indéterministe. Dans cet exemple,
on a les deux conditions.
Déroulement de l’algorithme 1 : L’état initial e0d regroupe tous les états initiaux.

a b c
→ e0d = {e0 , e3 }

A partir de e0 et e3 (on regarde les lignes de e0 et de e3 de la représentation tabulaire

de AEF I), avec le symbole a (on regarde la colonne de a), on va vers {e0 , e1 } qui
représente un nouvelle état e1d .

a b c
→ e0d = {e0 , e3 } e1d
e1d = {e0 , e1 }

A partir de e0 et e3 , avec le symbole b, on va vers {e1 , e3 } qui représente un nouvelle

état e2d . Avec un c, on va vers aucun état, on laisse alors la case vide.

a b c
→ e0d = {e0 , e3 } e1d e2d
e1d = {e0 , e1 }
e2d = {e1 , e3 }

On continue ensuite avec les états qui sont ajouter au fur et à mesure pour arriver à
l’automate à états finis de la figure 2.3 :

On remarque facilement que l’automate à états finis résultant (Table 2.3) est un auto-
mate déterministe, car on a une seule flèche entrante et au maximum un état par case
du tableau.

28 [Link]
 CHAPITRE 2. LANGAGES RÉGULIERS

a b c
→ e0d = {e0 , e3 } e1d e2d
e1d = {e0 , e1 } e1d e3d
e2d = {e1 , e3 } e2d e3d
← e3d = {e1 , e2 } e3d

Table 2.3: La représentation tabulaire de l’AEFD du langage L = a+ c+ ∪ b+ c+

[Link] Automates minimaux / non minimaux

Tout langage régulier est reconnu par au moins un automate à états finis déterministe
et complet.
Il en existe un ayant un nombre minimal d’états. Cet automate est unique : c’est
l’automate minimal du langage. L’intérêt d’un automate minimal est que le coût en
espace de la représentation est minimisé.
Pour tout automate à états finis non minimal, il existe un automate à états finis minimal
équivalent.
Il existe un algorithme (Algorithme 2) qui permet de passer d’un automate à états finis
complet, sans états inaccessibles et déterministe (AEF D) vers un automate à états finis
minimal (AEF M ). L’idée est d’essayer de faire du regroupement d’état, en fusionnant
plusieurs états.

Algorithme 2 : rendminimal
Entrée : AEF D = (A, Q, e0 , F, δ) {un automate à états finis déterministe, complet et
sans états inaccessibles}
Sortie : AEF M = (A, Qm , e0m , Fm , δm ) {tel que L(AEF D) = L(AEF M ) }
Séparer les états en deux groupes si c’est possible : G1 contenant les états finaux et
G2 contenant les états non finaux ;
Répéter
Si il existe un symbole a et deux états ei ∈ Q et ej ∈ Q d’un même groupe tel que
δ(ei , a) et δ(ej , a) n’appartiennent pas au même groupe alors
séparer ei et ej en deux groupes différents ; {On laisse dans le même groupe tous
les états qui donnent un état d’arrivée dans le même groupe}
Fin Si
Jusqu’à il n’y a plus de groupes à séparer
Les groupes sont les états de Qm ;
e0m ← Gi ∈ Qm /e0 ∈ Gi ; {L’état initial est le groupe qui contient l’état initial de
AEF D}
Fm sont tous les groupes qui dérivent de G1 ;
δm est l’ensemble δ en remplaçant les états de Q par le groupe qui les contient dans
Qm et en supprimant les transitions redondantes ;

29 [Link]
 CHAPITRE 2. LANGAGES RÉGULIERS

Pour la condition d’arrêt de la boucle de l’algorithme 2, on peut distinguer trois cas de

figure :
1. La dernière itération n’a pas changé les groupes.
2. Il existe un seul groupe. Ce groupe ne peut pas être divisé parce que toutes les
transitions vont vers des états de ce même groupe. Il existe deux cas de figure :
(a) Tous les états sont des états finaux : vu que l’automate est complet, cela revient
à reconnaitre tous les mots définis sur l’alphabet A. Le langage est alors A∗ .
(b) Aucun état n’est un état final : vu que l’automate est complet, cela revient à
ne reconnaitre aucun mot défini sur l’alphabet A. Le langage est alors ∅.
3. Tous les groupes sont constitués d’un seul état. Cela veut dire que l’automate
était minimal avant l’exécution de l’algorithme.
Pour dérouler cet algorithme, il est aussi pratique d’utiliser la représentation tabulaire
pour réduire le risque d’erreurs.

Exemples : Soit l’automate à états finis de la figure 2.6 à minimiser.

Figure 2.6: AEF à minimiser

On remarque qu’il n’existe pas d’état inaccessible, on passe alors à la représentation

tabulaire.
a b
→
← e0 e2 e1
← e1 e3 e0
← e2 e4 e1
← e3 e5 e0
e4 e4 e5
e5 e5 e5

Table 2.4: Représentation tabulaire de l’AEF à minimiser

30 [Link]
 CHAPITRE 2. LANGAGES RÉGULIERS

Avec la représentation tabulaire, on voit au premier coup d’œil que l’automate est
déterministe (une seule flèche entrante et maximum un état pas case) et complet (aucune
case vide).
On peut alors commencer le déroulement de l’algorithme de minimisation.
— G1 = {e0 , e1 , e2 , e3 }, G2 = {e4 , e5 } // initialement G1 contient les état finaux et
G2 le reste des états.
— G1 1 = {e0 , e1 }, G1 2 = {e2 , e3 }, G2 = {e4 , e5 } // ici, le premier groupe a été
divisé en deux groupes à cause des transitions avec le symbole a, les transitions
de e0 et e1 avec le a partent vers G1 alors que les transitions de e2 et e3 avec le
a partent vers G2. Donc l’ancien G1 a été divisé en deux groupes G1 1 et G1 2
alors que G2 ne s’est pas divisé.
— G1 1 = {e0 , e1 }, G1 2 = {e2 , e3 }, G2 = {e4 , e5 } // aucun changement lors de la
dernière itération, on sort de la boucle.
L’état initial est maintenant G1 1 (le groupe de e0 ).

Les états finaux sont G1 1 et G1 2 (les groupes qui dérivent de G1).

On obtient alors l’automate à états finis de la figure 2.7 :

Figure 2.7: AEF minimisé

Nous allons voir maintenant un second exemple avec l’automate à états finis suivant :

Figure 2.8: Exemple 2 d’AEF à minimiser

On remarque qu’il n’existe pas d’état inaccessible, on passe alors à la représentation

tabulaire.

Avec la représentation tabulaire, on remarque sans effort que l’automate est déterministe
et complet. On peut alors commencer le déroulement de l’algorithme de minimisation.
G1 = {e0 , e1 }

31 [Link]
 CHAPITRE 2. LANGAGES RÉGULIERS

a b
→
← e0 e1 e1
← e1 e1 e1

Table 2.5: Représentation tabulaire de l’automate de la figure 2.8

Fin de l’algorithme car il y a un seul état, on ne peut pas réduire plus, cet état est
l’état initial et l’état final. On obtient alors l’automate suivant :

Figure 2.9: AEF minimisé

2.4 Conclusion

Les langages réguliers sont générés par des grammaires régulières et les mots d’un
langage régulier peuvent être reconnus par un automate à états finis.
Il existe deux sortes de grammaires régulières équivalentes : les grammaires régulières à
droite et les grammaires régulières à gauche. Pour tout langage régulier, il est possible
d’avoir les deux sortes de grammaires.
Pour un langage régulier donné, il peut y avoir plusieurs automates à états finis déterministes
et / ou indéterministes qui reconnaissent les mots du langage. Il existe un algorithme
qui permet de passer de n’importe quel automate à états finis indéterministe à un au-
tomate à états finis déterministe équivalent. Il existe aussi un algorithme qui permet de
passer à l’automate à états finis minimal qui est unique à partir d’un automate à états
finis déterministe, complet et sans états inaccessibles.

32 [Link]
 CHAPITRE 2. LANGAGES RÉGULIERS

2.5 Exercices

Exercice 1 : Donner une grammaire régulière à droite, une grammaire régulière à

gauche un automate à états finis pour chacun des langages suivants :
— L1 = a+ b+
— L2 = a∗ cb∗
— L3 = (ab∗ )+
— L4 = a∗ b∗ c∗
— L5 = {m/m ∈ (a∗ b∗ )∗ et | m | mod 3 = 0}
— L6 = abc∗
— L7 = abc+
— L8 = (a∗ b∗ )(abc∗ ∪ c∗ )
— L9 = (ab ∪ ccb)(bac+ ∪ cc)
— L10 = {m/m ∈ (a∗ b∗ )∗ et | m |a mod 3 = 0}
— L11 = C(L1)

Exercice 2 : Quelles sont les langages générés par ces grammaires ?

1. G = (T, N, S, R)
T = {a, b, c}
N = {S, S 0 , S 00 }
R = {S → aS/bS 0 /cS 00 /ε, S 0 → bS 0 /cS 00 /ε, S 00 → cS 00 /ε}
2. G = (T, N, S 0 , R)
T = {a, b, c}
N = {S, S 0 }
R = {S → aS/ε, S 0 → aS 0 /bS 0 /ε}
3. G = (T, N, S, R)
T = {a, b, c}
N = {S, S 0 , S 00 , S 000 , S 0000 , S 00000 }
R={
S → aS/bS 0 /cS 00 /aS 000
S 0 → bS 0 /cS 0000
S 00 → cS 00 /aS 000
S 000 → bS 00000
S 0000 → b
S 00000 → c
}
4. G = (T, N, S, R)
T = {a, b, c}
N = {S, S 0 , S 00 }
R = {S → aS/bS 0 /cS 00 /c, S 0 → aS/bS 00 , S 00 → cS 00 /cS}

33 [Link]
 CHAPITRE 2. LANGAGES RÉGULIERS

Exercice 3 : Soit la grammaire régulière à droite suivante G = (T, N, S, R) avec :

T = {a, b, c}
N = {S, S 0 , S 00 }
R = {S → aS/aS 0 , S 0 → bS/cS 00 , S 00 → cS 00 /ε}

1. Les mots aabac, aaacc, aabbccc, ab appartiennent-ils à L(G).

2. Quel est le langage généré par cette grammaire ?
3. Donner une grammaire régulière à gauche pour ce langage.

Exercice 4 : Minimiser l’automate à états finis suivant :

34 [Link]
Chapitre 3

Langages algébriques

Les langages algébriques sont les langages de type 2. Ils sont générés par des gram-
maires algébriques. La reconnaissance des mots des langages algébriques se fait grâce
aux automates à pile. Un automate à pile a la particularité de posséder une mémoire
structurée en pile.

3.1 Langages algébriques

Un langage est algébrique si et seulement si : il existe une grammaire algébrique générant

ce langage.

3.1.1 Exemples de langages algébriques

La classe des langages algébriques inclus tous les langages réguliers ainsi que de nou-
veaux langages comme par exemple :
— an b n , n ≥ 0
— Le langage des mots palindromes : L = {m/m ∈ (a∗ b∗ )∗ et m = mr }
— Les expressions bien parenthésées : L = {m/m ∈ [(∗ )∗ ]∗ et | m |) =| m |( et ∀u, v
tel que m = uv alors | u |) ≤| u |( }

3.1.2 Propriétés de fermeture des langages algébriques

Si L1 et L2 sont des langages algébriques sur un alphabet A, alors les langages suivants
sont des langages algébriques :
— L1 ∪ L2 (L’union)
— L1L2 (La concaténation)
— L1∗ (L’étoile)
— L1r (L’image miroir)

35
 CHAPITRE 3. LANGAGES ALGÉBRIQUES

3.2 Grammaires algébriques

Les grammaires algébriques permettent de générer des langages algébriques.

3.2.1 Définition formelle

Une grammaire G = (T, N, S, R) est algébrique si les règles de R sont de la forme :

S → m avec S ∈ N et m ∈ (T ∪ N )∗

La seule restriction concerne la partie gauche de la règle qui doit être constituée d’un
seul symbole non terminal.

3.2.2 Exemple de grammaire algébrique

Soit un langage L = {an bn , n ≥ 0} défini sur l’alphabet A = {a, b}. Nous allons donner
une grammaire algébrique G(L).
G(L) = (T, N, S, R)
T = {a, b}
N = {S}
R = {S → aSb/ε}
Exemple de mot appartenant au langage L = {an bn , n ≥ 0} : aabb
Ce mot est obtenu en appliquant les règles de dérivation de R comme suit : S → aSb →
aaSbb → aabb
Exemple de mot n’appartenant pas au langage L = {an bn , n ≥ 0} : aab
ba : S → aSb. Ensuite, il reste à générer un a au milieu, mais il n’existe pas de règle
permettant de générer un a du type S → a. Donc, le mot aab ne peut pas être généré
par cette grammaire.

3.3 Automates à pile

Pour reconnaitre les mots des langages algébriques, on utilise des automates à pile.
Le principe de fonctionnement de l’automate à pile est le même que pour l’automate à
états finis auquel on va rajouter une mémoire structurée en pile.
La pile possède son propre alphabet noté P . On ne peut empiler et dépiler que les
symboles appartenant à P . De plus, on ne connait pas la taille de la pile et on a accès
uniquement à l’élément sommet de la pile. Lorsque le sommet est le mot vide (ε), cela
veut dire que la pile est vide.

36 [Link]
 CHAPITRE 3. LANGAGES ALGÉBRIQUES

3.3.1 Composition d’un automate à pile

Un automate à pile est composé de :

Une bande de lecture : La bande est composée d’une succession de cases. C’est
dans les cases de cette bande qu’est écrit le mot à reconnaı̂tre. Chaque case
pouvant contenir un seul symbole de l’alphabet d’entrée.
Une tête de lecture : La tête de lecture peut lire une case à un instant donné.
Une mémoire (une pile) : La pile possède un alphabet spécial. On peut empiler,
dépiler ou accéder au sommet de pile.
Une unité de contrôle : Elle est définie par un ensemble fini d’états ainsi que par
une fonction de transition qui décrit le passage d’un état à un autre en fonction
du contenu de la case courante, de l’état courant et du sommet de la pile. A
chaque fois qu’une transition s’exécute, la tête de lecture se déplace d’une seule
case vers la droite.

3.3.2 Définition formelle d’un automate à pile

Un automate à pile AP est un sextuplet AP = (A, P, Q, e0 , F, δ) :

A est l’alphabet des mots en entrée : c’est l’alphabet du langage des mots à
reconnaitre.
P est l’alphabet de pile : c’est les symboles qui sont stockés dans la pile.
Q est un ensemble non vide d’états : l’automate utilise entre autre les états
pour déterminer à quel étape il se trouve dans la reconnaissance des mots.
e0 ∈ Q est l’état initial : dans les automates à pile, on utilisera un seul état initial
par lequel l’automate commence la reconnaissance.
F ⊆ Q est un ensemble d’états finaux : ces états sont utilisé pour la reconnais-
sance des mots du langage.
δ est un ensemble de transitions : les transitions permettent de faire des éventuelles
changements d’états à la lecture d’un symbole et/ou de faire des actions sur la
pile.

3.3.3 Procédure de reconnaissance dans les automates à pile

La reconnaissance des mots par l’automate à pile commence par l’état initial et une
pile vide.
Un mot est reconnu par un automate à pile si est seulement si à la fin de la lecture du
mot, on est dans un état final et la pile est vide.
Il existe d’autres type d’automates à pile qui font la reconnaissance par pile vide ou par
état final. Ces types ne sont pas traités dans ce cours.

37 [Link]
 CHAPITRE 3. LANGAGES ALGÉBRIQUES

3.3.4 Représentation des automates à pile

Pour les automates à pile, nous n’utiliserons que la représentation formelle.

Dans un automate à pile, à la lecture d’un symbole d’un mot, l’automate se trouve
dans un état appartenant à Q et le sommet de pile contient un symbole de P (ou bien
ε lorsque la pile est vide). Il effectue alors une transition pour éventuellement changer
d’état et / ou l’état de la pile. Les transitions sont écrites sous la forme suivante :
(état source, symbole lu, sommet de pile) → (état destination, opération sur la pile)

3.3.5 Opérations sur la pile lors des transitions dans les automates à pile

Soit un automate à pile AP = (A, P, Q, e0 , F, δ) avec a ∈ A ; ei , ej ∈ Q et A, B ∈ P

La fonction empiler :
(ei , a, A) → (ej , AB) : si on est dans l’état ei et on lit un a et le sommet de pile est
un A alors on passe à ej et on empile un B.
(ei , a, ε) → (ej , B) : si on est dans l’état ei et on lit un a et la pile est vide alors on
passe à ej et on empile un B.

La fonction dépiler :
(ei , a, A) → (ej , ε) : si on est dans l’état ei et on lit un a et le sommet de pile est un
A alors on passe à ej et on dépile un A.
On ne peut pas dépiler si la pile est vide.

Transitions sans modifier la pile :

(ei , a, A) → (ej , A) : si on est dans l’état ei et on lit un a et le sommet de pile est
un A alors on passe à ej sans modifier la pile.
(ei , a, ε) → (ej , ε) : si on est dans l’état ei et on lit un a et le sommet de pile est
vide alors on passe à ej sans modifier la pile.

Exemple : Soit un langage L = {an bn , n ≥ 0} défini sur l’alphabet A = {a, b}. Nous
allons donner une représentation formelle de l’automate à pile AP (L).
L’idée est de compter le nombre de symbole a grâce à la pile. A chaque lecture d’un
symbole a, on empile un symbole A. Pour vérifier qu’on a le même nombre de a que de
b. On dépile un A à chaque lecture d’un b. Lorsque la pile est vide, on aura atteint le
même nombre de a que de b.
AP = (A, P, Q, e0 , F, δ)
A = {a, b}
P = {A}
Q = {e0 , e1 }

38 [Link]
 CHAPITRE 3. LANGAGES ALGÉBRIQUES

F = {e0 , e1 }
δ={
(e0 , a, ε) → (e0 , A),
(e0 , a, A) → (e0 , AA),
(e0 , b, A) → (e1 , ε),
(e1 , b, A) → (e1 , ε)
}
Exemple de mot appartenant au langage L = {an bn , n ≥ 0} : aabb
Au début, l’automate se trouve à l’état initial e0 et la pile est vide. La tête de lecture
est sur le premier symbole du mot à savoir a. Il existe une transition qui va de cette
configuration vers l’état e0 et un A est empilé dans la pile ((e0 , a, ε) → (e0 , A)). La tête
de lecture se situe alors sur le deuxième symbole du mot à savoir un a, et l’automate
est resté dans l’état e0 et la pile contient un A. L’automate va alors faire passer par
la transition (e0 , a, A) → (e0 , AA). La tête de lecture se situe alors sur le troisième
symbole du mot à savoir un b, et l’automate est resté dans l’état e0 et la pile contient
deux symboles A. Il existe une transition qui va de cette configuration vers l’état e1
et un A va être dépilé ((e0 , b, A) → (e1 , ε)). La tête de lecture se situe alors sur le
quatrième symbole du mot à savoir un b, et l’automate est passé à l’état e1 et la pile
contient un A. Il existe une transition qui va de cette configuration vers l’état e1 et
un A va être dépilé ((e1 , b, A) → (e1 , ε)). Le mot est terminé et l’automate se trouve
dans l’état e1 qui est un état final, et la pile est vide. Le mot est alors reconnu par
l’automate.
Exemple de mot n’appartenant pas au langage L = {an bn , n ≥ 0} : aab
L’automate va avoir exactement le même comportement que le premier exemple sauf
que le mot va se terminer alors que l’automate se trouve sur l’état e1 et la pile contient
un A. L’état e1 est un état final, mais la pile n’est pas vide. Le mot est alors non reconnu
par l’automate.
On peut aussi avoir des mots avec plus de b que de a comme par exemple abb. Dans ce cas
l’automate va faire des empilement lorsqu’il rencontre des a puis des dépilement lorsqu’il
rencontre des b, sauf que lorsqu’il va faire autant de dépilement que d’empilement,
l’automate va se trouver dans l’état e1 et il va lire un b (il y a plus de b que de a)
et la pile sera vide. Il va alors y avoir un blocage. Le mot est alors non reconnu par
l’automate.

3.3.6 Automates à pile indéterministes

Dans les automates à pile, il y a un seul état initial. Le seul cas possible pour avoir un
automate à pile indéterministe est qu’à partir d’un état donné, un état de pile donné et
un symbole lu, on a deux transitions possibles. Nous allons illustrer le cas des automates
à pile indéterministes par l’exercice suivant :

39 [Link]
 CHAPITRE 3. LANGAGES ALGÉBRIQUES

Exercice : Donner le langage, la grammaire et l’automate à pile du langage des mots

palindromes constitués des symboles {a, b}.

Solution : Un mot palindrome est un mot qui se lit de gauche à droite ou de droite à
gauche de la même façon. C’est donc un mot qui est égal à son image miroir.
L = {m/m = mr et m ∈ (a∗ b∗ )∗ }
G(L) = (T, N, S, R)
T = {a, b}
N = {S}
R = {S → aSa/bSb/ε/a/b}
Il existe une grammaire algébrique pour ce langage donc ce langage est algébrique.
L’idée pour faire un automate à pile du langage des mots palindrome est déjà de définir
le langage différemment :
L = {mmr ∪ mamr ∪ mbmr /m ∈ (a∗ b∗ )∗ }
Ce dernier langage est équivalent au premier sauf qu’il nous permet de voir les différents
cas possibles. Avec cette écriture, on peut remarquer que le dernier symbole de m est
égal au premier symbole de mr et l’avant dernier symbole de m est égal au deuxième
symbole de mr et ainsi de suite jusqu’au premier symbole de m qui est égal au dernier
symbole de mr . C’est le principe même de la pile (dernier entrée- premier sortie). On
va alors faire des empilements à la lecture de m et des dépilements à la lecture de mr .
Sauf qu’on a trois cas (un mot de taille paire, un mot de taille impaire avec un a au
milieu, un mot de taille impaire avec un b au milieu) et qu’on est incapable de savoir à
la lecture d’un mot dans quel cas on se trouve. Pire encore, on n’a pas la possibilité de
savoir à quel moment on a terminé m pour arrêter d’empiler et commencer à dépiler.
La solution est de faire un automate à pile indéterministe.
L’automate à pile indéterministe de L est comme suit :
AP (L) = (A, P, Q, e0 , F, δ)
A = {a, b}
P = {A, B}
Q = {e0 , e1 }
F = {e0 , e1 }
δ={
(e0 , a, ε) → (e0 , A),
(e0 , b, ε) → (e0 , B),
(e0 , a, ε) → (e1 , ε),
(e0 , b, ε) → (e1 , ε),
(e0 , a, A) → (e0 , AA),
(e0 , a, B) → (e0 , BA),
(e0 , b, A) → (e0 , AB),

40 [Link]
 CHAPITRE 3. LANGAGES ALGÉBRIQUES

(e0 , b, B) → (e0 , BB),

(e0 , a, A) → (e1 , ε),
(e0 , b, B) → (e1 , ε),
(e0 , a, A) → (e1 , A),
(e0 , a, B) → (e1 , B),
(e0 , b, A) → (e1 , A),
(e0 , b, B) → (e1 , B),
(e1 , a, A) → (e1 , ε),
(e1 , b, B) → (e1 , ε)
}
Exemple de mot appartenant au langage L = {mmr ∪ mamr ∪ mbmr /m ∈ (a∗ b∗ )∗ } : a
Au début, l’automate se trouve dans l’état initial e0 et la pile est vide. La tête de lecture
est sur le premier symbole du mot à savoir a. Il existe deux transitions à partir de cette
configuration. il faut alors tester les deux chemins :
Chemin 1 : (e0 , a, ε) → (e0 , A), le mot est alors terminé et l’automate se trouve
sur l’état e0 et la pile contient un A. L’état e0 n’est pas un état final et la pile
n’est pas vide. Donc, ce chemin ne permet pas de reconnaitre le mot.
Chemin 2 : (e0 , a, ε) → (e1 , ε), le mot est alors terminé et l’automate se trouve sur
l’état e1 et la pile est vide. L’état e1 est un état final et la pile est vide. Donc, ce
chemin permet de reconnaitre le mot.
Le mot a est reconnu par l’automate car il y a au moins un chemin qui a reconnue le
mot.
Exemple de mot n’appartenant pas au langage L = {mmr ∪ mamr ∪ mbmr /m ∈
(a∗ b∗ )∗ } : ab
Au début, l’automate se trouve dans l’état initial e0 et la pile est vide. La tête de lecture
est sur le premier symbole du mot à savoir a. Il existe deux transitions à partir de cette
configuration. il faut alors tester les deux chemins :
Chemin 1 : (e0 , a, ε) → (e0 , A), la tête de lecture est sur le deuxième symbole à
savoir le b, l’automate est dans l’état e0 et la pile contient un A. Il existe deux
transitions à partir de cette configuration. il faut les tester les deux :
Chemin 1.1 : (e0 , b, A) → (e0 , AB), le mot est alors terminé et l’automate se
trouve sur l’état e0 et la pile n’est pas vide. L’état e0 n’est pas un état final et
la pile n’est pas vide. Donc, ce chemin ne permet pas de reconnaitre le mot.
Chemin 1.2 : (e0 , b, A) → (e1 , A), le mot est alors terminé et l’automate se
trouve sur l’état e1 et la pile n’est pas vide. L’état e1 est un état final mais
comme la pile n’est pas vide, ce chemin ne permet pas de reconnaitre le mot.
Chemin 2 : (e0 , a, ε) → (e1 , ε), la tête de lecture est sur le deuxième symbole à
savoir le b, l’automate est dans l’état e1 et la pile est vide. Il n’existe aucune
transition à partir de cette configuration. Donc, ce chemin ne permet pas de
reconnaitre le mot.

41 [Link]
 CHAPITRE 3. LANGAGES ALGÉBRIQUES

Le mot ab n’est pas reconnu par l’automate car il n’existe aucun chemin qui permette
de reconnaitre le mot ab.
Il existe un automate à pile pour reconnaitre n’importe quel langage algébrique. Par
contre, il n’existe pas nécessairement un automate à pile déterministe pour tous les
langages algébriques.
Il n’existe pas d’algorithme permettant de passer de l’automate à pile indéterministe à
l’automate à pile déterministe.
La classe des langages reconnus par un automate à pile déterministe est incluse dans
la classe des langages algébriques mais n’est pas égale. Ce qui signifie qu’il existe des
langages algébriques qui ne possèdent pas d’automates à pile déterministe reconnaissant
les mots de ces langages.

3.4 Conclusion

Les langages algébriques sont générés par des grammaires algébriques et les mots d’un
langage algébrique peuvent être reconnus par un automate à pile.
Les grammaires algébriques ont une seule contrainte, c’est que la partie gauche de la
règle doit être constituée d’un seul symbole non terminal.
Les automates à pile déterministe ne peuvent pas reconnaitre les mots de tous les
langages algébriques. Par contre, pour tout langage algébrique, il existe au moins un
automate déterministe ou indéterministe qui reconnait les mots du langage.
En raison de la relation d’inclusion entre les langages (voir figure 1.1), il existe une
grammaire algébrique pour générer n’importe quel langage régulier et un automate à
pile pour reconnaitre les mots d’un langage régulier.

42 [Link]
 CHAPITRE 3. LANGAGES ALGÉBRIQUES

3.5 Exercices

Donner les grammaires ainsi que les automates à pile des langages sui-
Exercice 1 :
vants :
— L1 = {an bn cm dm , n > 0 et m > 0}
— L2 = {an bm cm dn , n > 0 et m > 0}

Exercice 2 : Définir formellement les langages suivants puis donner leurs grammaires
ainsi que leurs automates à pile :
— L1 = les mots palindromes constitués des symboles a, b et un seul c au milieu du
mot.
— L2 = L3L4 tel que :

— L3 est constitué des symboles a et b et le nombre de symbole a est égal au

nombre de symbole b.
— L4 est constitué des symboles c et d et le nombre de symbole c est égal au
nombre de symbole d.

Exercice 3 : Une équipe de cryptographes décide d’introduire une règle pour les mes-
sages codés (une signature), les messages qui doivent être décryptés sont uniquement
les messages constitués d’un même nombre de symboles ”?” que de symboles ”!”.
Les autres sont rejetés. Les messages peuvent aussi contenir les symboles suivants
{1, 2, a, b}.
1. Donner un automate à pile permettant de savoir si un message doit être décrypté
ou non.
2. Définir formellement le langage L reconnu par l’automate à pile.
3. Donner la grammaire G(L).

Exercice 4 : QCM
1. Soient les langages suivants, lesquels désignent un langage de mots palindromes ?
a) L1 = {mamr /m ∈ (a∗ b∗ )∗ }
b) L2 = {mmr /m ∈ (a∗ b∗ )∗ }
c) L3 = {m/m ∈ (a∗ b∗ )∗ et m = mr }
d) L4 = {mcmr /m ∈ (a∗ b∗ )∗ }
2. Lorsqu’il existe un automate à pile indéterministe, il existe un automate à pile
déterministe équivalent.
a) Vrai
b) Faux

43 [Link]
 CHAPITRE 3. LANGAGES ALGÉBRIQUES

3. Le langage L = {an bm , n < m} est reconnaissable par un automate à pile

déterministe.
a) Vrai
b) Faux
4. Le langage L = {an bm , n, m > 0} est reconnaissable par un automate à pile
déterministe.
a) Vrai
b) Faux
5. Le langage L = {an bm , n > m} est reconnaissable par un automate à pile
déterministe.
a) Vrai
b) Faux

44 [Link]
Chapitre 4

Langages contextuels

Les langages contextuels sont les langages de type 1, ils sont générés par des grammaires
de type 1. Il existe deux types de grammaires de type 1, les grammaires monotones et
les grammaires contextuelles. La reconnaissance des mots des langages contextuels se
fait grâce aux machines de Turing à bornes linéaires.

4.1 Langages contextuels

Un langage est contextuel si et seulement si : il existe une grammaire de type 1 générant

ce langage.

4.1.1 Exemples de langages contextuels

La classe des langages contextuels inclus tous les langages algébriques ainsi que de
nouveaux langages comme par exemple :
— an b n c n , n ≥ 0
n
— a2 , n ≥ 0

4.1.2 Propriétés de fermeture des langages contextuels

Si L1 et L2 sont des langages contextuels sur un alphabet A, alors les langages suivants
sont des langages contextuels :
— L1 ∪ L2 (L’union)
— L1L2 (La concaténation)
— L1∗ (L’étoile)
— L1 ∩ L2 (L’intersection)
— C(L1) (Le complément)

45
 CHAPITRE 4. LANGAGES CONTEXTUELS

4.2 Grammaires de type 1

Les grammaires de type 1 permettent de générer des langages contextuels.

4.2.1 Définition formelle

Il existe deux types de grammaires de type 1 équivalentes :

Grammaire contextuelle : Une grammaire G = (T, N, S, R) est contextuelle si
les règles de R sont de la forme :
uSv → umv avec S ∈ N , u, v ∈ (T ∪ N )∗ et m ∈ (T ∪ N )+
Le symbole non terminal S est remplacé par m tout en gardant le préfixe u à
gauche et le suffixe v à droite.
Grammaire monotone : Une grammaire G = (T, N, S, R) est monotone si les
règles de R sont de la forme :
u → v avec u, v ∈ (T ∪ N )+ et | u |≤| v |
On remarque en analysant les deux définitions précédentes qu’il n’est pas possible
d’avoir de règle permettant de générer le mot vide.
En effet, dans la grammaire contextuelle, on a u et v qui peuvent prendre ε mais pas
m (m ∈ (T ∪ N )+ ). Dans la grammaire monotone, on a u → v avec u, v ∈ (T ∪ N )+ .
Pour pouvoir générer le mot vide par une grammaire de type 1 d’un langage qui contient
le mot vide, il y a une condition supplémentaire sur les règles qui est :
Si (S → ε) ∈ R, S étant l’axiome, alors S n’apparait pas en partie droite d’une autre
règle.
Et (S 0 → ε) ∈
/ R, ∀S 0 ∈ N et S 0 6= S.

4.2.2 Exemples de grammaires de type 1

Soit un langage L = an bn cn , n ≥ 0 défini sur l’alphabet A = {a, b, c}. Nous donnons

une grammaire monotone Gm (L) et une grammaire contextuelle Gc (L).
La grammaire monotone Gm (L) :
Gm (L) = (T, Nm , Sm , Rm )
T = {a, b, c}
Nm = {Sm , X, Y }
Rm = {
Sm → aXbc/abc/ε,
X → aXY b/aY b,
Y b → bY,
Y c → cc
}

46 [Link]
 CHAPITRE 4. LANGAGES CONTEXTUELS

Voici un exemple de génération de mot (aaabbbccc) avec la grammaire monotone Gm (L) :

X→aXY b X→aY b Y b→bY Y b→bY

Sm → aXbc → aaXY bbc → aaaY bY bbc → aaabY Y bbc → aaabY bY bc

Y b→bY Y b→bY Y b→bY Y c→cc Y c→cc

→ aaabbY Y bc → aaabbY bY c → aaabbbY Y c → aaabbbY cc → aaabbbccc

On peut vérifier que cette grammaire est une grammaire monotone. En effet, on a :
— Sm → ε. Sm est bien l’axiome, et Sm n’apparait pas en partie droite d’une autre
règle.
— Sm → aXbc. | Sm |≤| aXbc |
— Sm → abc. | Sm |≤| abc |
— X → aXY b. | X |≤| aXY b |
— X → aY b. | X |≤| aY b |
— Y b → bY . | Y b |≤| bY |
— Y c → cc. | Y c |≤| cc |

La grammaire contextuelle Gc (L) :

Gc (L) = (T, Nc , Sc , Rc )
T = {a, b, c}
Nc = {Sc , A, B, C, D, E}
Rc = {
Sc → aABc/abc/ε,
A → aACB/aCB,
B → b,
Cc → cc,
CB → DB,
DB → DE,
DE → BE,
BE → BC
}

Dans la grammaire contextuelle, il n’est pas possible d’avoir des règle du type CB →
BC, c’est pourquoi nous avons utiliser 4 règles pour passer de CB à BC en utilisant
les symboles non terminaux D et E.

Voici un exemple de génération de mot (aaabbbccc) avec la grammaire contextuelle

Gc (L) :

47 [Link]
 CHAPITRE 4. LANGAGES CONTEXTUELS

A→aACB A→aCB CB→DB DB→DE

Sc → aABc → aaACBBc → aaaCBCBBc → aaaDBCBBc →

DE→BE BE→BC ∗ ∗
aaaDECBBc → aaaBECBBc → aaaBCCBBc → aaaBCBCBc →

∗ ∗ B→b B→b B→b

aaaBBCCBc → aaaBBCBCc → aaaBBBCCc → aaabBBCCc → aaabbBCCc →

Cc→cc Cc→cc
aaabbbCCc → aaabbbCcc → aaabbbccc
On peut facilement vérifier que cette grammaire est une grammaire contextuelle. En
effet, on va donner pour chaque règle le préfixe u et le suffixe v :
— Sc → ε. Sc est bien l’axiome, et Sc n’apparait pas en partie droite d’une autre
règle.
— Sc → aABc. u = v = ∅
— Sc → abc. u = v = ∅
— A → aACB. u = v = ∅
— A → aCB. u = v = ∅
— B → b. u = v = ∅
— Cc → cc. u = ∅, v = c
— CB → DB. u = ∅, v = B
— DB → DE. u = D, v = ∅
— DE → BE. u = ∅, v = E
— BE → BC. u = B, v = ∅

4.3 Machines de Turing à bornes linéaires

Pour reconnaitre les mots des langages contextuels, on utilise des automates particuliers
appelés : machines de Turing à bornes linéaires.
Les machines de Turing à bornes linéaires utilise le principe de marquage (Les symboles
des mots sont remplacés par d’autres symboles) dans la procédure de reconnaissance.

4.3.1 Composition d’une Machine de Turing à bornes linéaires

Les composants d’une machine de Turing à bornes linéaires sont :

Une bande de lecture/écriture : Contrairement aux automates vus jusque là, la
bande de lecture d’une machine de Turing à bornes linéaires est aussi une bande
d’écriture. Chaque case pouvant contenir un seul symbole de l’alphabet d’entrée
ou de l’alphabet auxiliaire d’écriture.
Une tête de lecture/écriture : La tête de lecture peut lire une case à un instant
donné mais aussi écrire dans une case. La tête peut être déplacée par la machine
de Turing à bornes linéaires pour se positionner sur la case immédiatement à
gauche ou à droite de la case courante.

48 [Link]
 CHAPITRE 4. LANGAGES CONTEXTUELS

Une unité de contrôle : Elle est définie par un ensemble fini d’états ainsi que par
une fonction de transition qui décrit le passage d’un état à un autre en fonction
du contenu de la case courante de la bande de lecture et de l’état dans lequel se
trouve la machine de Turing à bornes linéaires. L’unité de contrôle décide aussi
de la direction dans laquelle il faut déplacer la tête de lecture/écriture.

4.3.2 Définition formelle d’une Machine de Turing à bornes linéaires

Une machine de Turing à bornes linéaires M T ABL est un septuplet :

AP = (A, X, ], Q, e0 , ef , δ) :
A est l’alphabet des mots en entrée : c’est l’alphabet du langage des mots à
reconnaitre.
X est l’alphabet auxiliaire d’écriture : c’est les symboles qui sont utilisés pour
le marquage.
] est le symbole qui marque la fin de bande à droite et à gauche : Le mot
à reconnaitre m se trouve sur la bande de lecture/écriture entre deux symboles ].
On a donc toujours ]m].
Q est un ensemble non vide d’états : Utilisé entre autre pour déterminer à quel
étape se trouve la machine de Turing à bornes linéaires dans la reconnaissance
des mots.
e0 ∈ Q est l’état initial : État par lequel la machine de Turing à bornes linéaires
commence la reconnaissance.
ef ∈ Q est un état final : Il y a la possibilité d’utiliser un seul état final dans
machine de Turing à bornes linéaires.
δ est un ensemble de transitions : Les transitions permettent de faire certaines
actions à la lecture d’un symbole, comme par exemple le changement d’état,
l’écriture ou le changement de direction de la tête de lecture/écriture.

4.3.3 Procédure de reconnaissance dans les machines de Turing à bornes

linéaires

Le mot à reconnaitre se trouve sur la bande de lecture/écriture entre deux symboles ].

Un symbole ] à gauche du mot et un autre à droite du mot. La reconnaissance des mots
par une machine de Turing commence par l’état initial et la tête de lecture/écriture se
trouve sur le premier symbole du mot ou bien sur le symbole ] de droite si le mot est
vide. Un mot est reconnu si à la fin, on se trouve dans un état final est que la tête de
lecture/écriture se trouve à droite du symbole ] de droite. Une machine de Turing à
borne linéaire ne peut pas utiliser les cases qui précèdent le ] de gauche ou les cases qui
suivent le ] de droite pour la reconnaissance.

49 [Link]
 CHAPITRE 4. LANGAGES CONTEXTUELS

4.3.4 Représentation des machines de Turing à bornes linéaires

Concernant les machines de Turing à bornes linéaires, nous allons utiliser uniquement
la représentation tabulaire qui est comme suit :
— Chaque ligne représente un état.
— Chaque colonne représente un symbole de l’alphabet du langage ou de l’alphabet
auxiliaire ou bien le symbole ].
— L’état initial est marqué par une flèche entrante et l’état final par une flèche
sortante.
— Les cases du tableau sont constituées de triplets (état destination, le symbole
écrit, la direction). La direction est soit D pour droite ou G pour gauche.

Exemple : Soit un langage L = {an bn cn , n ≥ 0} défini sur l’alphabet A = {a, b, c}.

Nous allons donner une représentation tabulaire de la machine de Turing à bornes
linéaires M T ABL(L).
L’idée est de marquer un symbole a avec un symbole A. Ensuite, il faut traverser les
autres sans les marquer jusqu’à arriver au premier symbole b qui est marqué à son tour
par un B. Ensuite, il faut traverser les autres sans les marquer jusqu’à arriver au pre-
mier symbole c qui est marqué à son tour par un C. Après, il faut revenir au deuxième
a pour refaire la même procédure de marquage. Donc à chaque tour, un a, un b et un
c sont marqués. Donc, lorsque les a se terminent, les autres symboles doivent être tous
marqués (il n’y a plus de symboles a, b, c sur la bande de lecture/écriture).
a b c A B C ]
→ e0 (e1 , A, D) (e4 , B, D) (ef , ], D)
e1 (e1 , a, D) (e2 , B, D) (e1 , B, D)
e2 (e2 , b, D) (e3 , C, G) (e2 , C, D)
e3 (e3 , a, G) (e3 , b, G) (e0 , A, D) (e3 , B, G) (e3 , C, G)
e4 (e4 , B, D) (e4 , C, D) (ef , ], D)
← ef

Exemple de mot appartenant au langage L = {an bn cn , n ≥ 0} : aabbcc

Le mot se trouve entre deux symboles ] dans la bande de lecture/écriture (]aabbcc]).
Initialement la machine de Turing à bornes linéaires se trouve à l’état initial e0 et la tête
de lecture/écriture sur le premier symbole du mot à savoir a. Il existe une transition qui
va de cette configuration vers l’état e1 avec le marquage du symbole a avec le symbole
A et la tête de lecture/écriture se déplace à droite(]Aabbcc]). La tête de lecture se situe
alors sur le deuxième symbole du mot à savoir un a, et la machine de Turing à bornes
linéaires est à l’état e1 . Il existe une transition qui va de cette configuration vers l’état
e1 sans marquage et la tête de lecture/écriture se déplace à droite(]Aabbcc]). La tête
de lecture se situe alors sur le troisième symbole du mot à savoir un b, et la machine
de Turing à bornes linéaires est à l’état e1 . Il existe une transition qui va de cette
configuration vers l’état e2 avec le marquage du symbole b avec le symbole B et la tête
de lecture/écriture se déplace à droite(]AaBbcc]). La tête de lecture se situe alors sur

50 [Link]
 CHAPITRE 4. LANGAGES CONTEXTUELS

le quatrième symbole du mot à savoir un b, et la machine de Turing à bornes linéaires

est à l’état e2 . Il existe une transition qui va de cette configuration vers l’état e2 sans
marquage et la tête de lecture/écriture se déplace à droite(]AaBbcc]). La tête de lecture
se situe alors sur le cinquième symbole du mot à savoir un c, et la machine de Turing à
bornes linéaires est à l’état e2 . Il existe une transition qui va de cette configuration vers
l’état e3 avec le marquage du symbole c avec le symbole C et la tête de lecture/écriture
se déplace à gauche(]AaBbCc]). La machine de Turing à bornes linéaires est à l’état
e3 , elle va aller à gauche tant qu’elle ne rencontre pas de symbole A.
A la lecture d’un A, la machine de Turing à bornes linéaires se déplace à droite et
revient à état e0 pour un nouveau cycle de marquage pour obtenir le marquage suivant
]AABBCC]. Après le marquage du dernier symbole c. La machine de Turing à bornes
linéaires est à l’état e3 , elle va aller à gauche tant qu’elle ne rencontre pas de symbole
A.
A la lecture d’un A, la machine de Turing à bornes linéaires se déplace à droite et
revient à état e0 et trouve un symbole B. A la lecture d’un B, la machine de Turing à
bornes linéaires se déplace à droite et va à état e4 . Il ne reste que des symbole B et C
avant le ], ils vont être parcourus avec l’état e4 , et à la rencontre du ] la machine de
Turing à bornes linéaires se déplace à droite et va à état ef . Le mot est donc reconnu.

4.3.5 Machines de Turing à bornes linéaires indéterministes

On peut avoir des machines de Turing à bornes linéaires indéterministes pour les lan-
gages contextuels. Dans une Machine de Turing à bornes linéaires indéterministe, on
a au moins une case qui contient deux transitions (deux triplets). Par contre, contrai-
rement aux langages de type 2, la classe des langages reconnus par une machine de
Turing à bornes linéaires déterministe est équivalentes à la classe des langages contex-
tuels. Donc, si L est un langages contextuel alors, il existe une machine de Turing à
bornes linéaires déterministe reconnaissant les mots de L.

4.4 Conclusion

Les langages contextuels sont générés par des grammaires de type 1 et les mots d’un
langage contextuel peuvent être reconnus par une machine de Turing à bornes linéaires.
Il existe deux sortes de grammaires de type 1 équivalentes : les grammaires monotones
et les grammaires contextuelles. Pour tout langage contextuel, il est possible d’avoir les
deux sortes de grammaires.
Nous nous sommes focalisés dans ce chapitre sur les machines de Turing à bornes
linéaires qui représentent la partie la plus importante du chapitre. Nous avons vu qu’on
pouvait avoir une machine de Turing à bornes linéaires déterministe pour tout langage
contextuel, et qu’on pouvait avoir un seul état initial et un seul état final avec ce type
de reconnaisseur.

51 [Link]
 CHAPITRE 4. LANGAGES CONTEXTUELS

4.5 Exercices

Exercice 1 : Faire une machine de Turing à borne linéaire pour chacun des langages
suivants :
— L1 = {an bm cn dm |n, m > 0}
— L2 = {a3n b2n cn , n > 0}
n
— L3 = {a2 , n ≥ 0}
— L4 = {m/m ∈ (a∗ b∗ c∗ )∗ et | m |a =| m |b =| m |c }

52 [Link]
Chapitre 5

Langages récursivement
énumérables et calculabilité

Les langages récursivement énumérables sont les langages de type 0. Ils sont générés par
des grammaires sans restriction. La reconnaissance des mots des langages récursivement
énumérables se fait grâce aux machines de Turing. Nous allons voir à la fin de ce chapitre
comment les machines de Turing sont aussi utilisées pour la calculabilité.

5.1 Langages récursivement énumérables

Un langage L est récursivement énumérable si et seulement si il existe une grammaire

de type 0 générant ce langage.
Un langage L est récursivement énumérables si et seulement si il existe une machine de
Turing reconnaissant ce langage.

5.1.1 Exemples de langages récursivement énumérables

La classe des langages récursivement énumérables inclus tous les langages contextuels
ainsi que de nouveaux langages comme par exemple :
— L = {n/n ∈ 1(0∗ 1∗ )∗ ∪ 0 et La valeur entière de n représenté en binaire est
divisible par 3}

5.1.2 Propriétés de fermeture des langages récursivement énumérables

Si L1 et L2 sont des langages récursivement énumérables sur un alphabet A, alors les

langages suivants sont des langages récursivement énumérables :
— L1 ∪ L2 (L’union)
— L1L2 (La concaténation)
— L1∗ (L’étoile)
— L1 ∩ L2 (L’intersection)

53
 CHAPITRE 5. LANGAGES RÉCURSIVEMENT ÉNUMÉRABLES ET CALCULABILITÉ

5.2 Grammaires sans restriction

La grammaire de type 0 est une grammaire sans restriction :

5.2.1 Définition formelle

Une grammaire sans restriction est une grammaire G = (T, N, S, R) telle que les règles
de R sont de la forme :

u → v avec u ∈ (T ∪ N )+ , v ∈ (T ∪ N )∗

La seule restriction est qu’on ne peut pas générer un mot à partir du mot vide.

5.2.2 Exemple de grammaire sans restriction

n
Soit un langage L = a2 , n ≥ 0 défini sur l’alphabet A = {a}. Nous allons donner deux
grammaire pour ce langage G1 (L) et G2 (L).
G1 (L) = (T, N1 , S1 , R1 )
T = {a}
N1 = {S1 , D1 , X1 , F1 , Y1 , Z1 }
R1 = {
S1 → D1 X1 aF1 /a,
X1 a → aaX1 ,
X1 F 1 → Y1 F 1 ,
X1 F1 → Z1 ,
aY1 → Y1 a,
D1 Y1 → D1 X1 ,
aZ1 → Z1 a,
D1 Z1 → ε
}

Voici un exemple de génération de mot (aaaaaaaa) avec la grammaire G1 (L) :

X1 a→aaX1 X1 F1 →Y1 F1 aY1 →Y1 a aY1 →Y1 a

S1 → D1 X1 aF1 → D1 aaX1 F1 → D1 aaY1 F1 → D1 aY1 aF1 →

D1 Y1 →D1 X1 X1 a→aaX1 X1 a→aaX1 X1 F1 →Y1 F1

D1 Y1 aaF1 → D1 X1 aaF1 → D1 aaX1 aF1 → D1 aaaaX1 F1 →

aY1 →Y1 a ∗ D1 Y1 →D1 X1 X1 a→aaX1

D1 aaaaY1 F1 → D1 aaaY1 aF1 → D1 Y1 aaaaF1 → D1 X1 aaaaF1 →

54 [Link]
 CHAPITRE 5. LANGAGES RÉCURSIVEMENT ÉNUMÉRABLES ET CALCULABILITÉ

∗ X1 F1 →Z1 aZ1 →Z1 a

D1 aaX1 aaaF1 → D1 aaaaaaaaX1 F1 → D1 aaaaaaaaZ1 → D1 aaaaaaaZ1 a

aZ1 →Z1 a ∗ D1 Z1 →ε
→ D1 aaaaaaZ1 aa → D1 Z1 aaaaaaaa → aaaaaaaa

De quel type est cette grammaire ?

— Cette grammaire n’est pas de type 3 (S1 → D1 X1 aF1 )
— Cette grammaire n’est pas de type 2 (X1 a → aaX1 )
— Cette grammaire n’est pas de type 1 (X1 F1 → Z1 )
— Cette grammaire est de type 0
G2 (L) = (T, N2 , S2 , R2 )
T = {a}
N2 = {S2 , D2 , X2 , F2 , Y2 }
R2 = {

S2 → D2 Y2 F2 /aa/a,
Y2 → X2 Y2 ,
X2 aa → aaX2 a,
D2 aaa → aaD2 aa,
Y2 → aa,
X2 aF2 → aaF2 ,
D2 aaF2 → aaaa
}
Voici un exemple de génération de mot (aaaaaaaa) avec la grammaire G2 (L) :

Y2 →X2 Y2 Y →aa X2 aa→aaX2 a X2 aF2 →aaF2

S2 → D2 Y2 F2 → D2 X2 Y2 F2 2→ D2 X2 aaF2 → D2 aaX2 aF2 →

D2 aaa→aaD2 aa D2 aaa→aaD2 aa D2 aaF2

D2 aaaaF2 → aaD2 aaaF2 → aaaaD2 aaF2 → aaaaaaaa

De quel type est cette grammaire ?

— Cette grammaire n’est pas de type 3 (S2 → D2 Y2 F2 )
— Cette grammaire n’est pas de type 2 (X2 aa → aaX2 a)
— Cette grammaire est de type 1 (grammaire monotone)
Pour le même langage L, nous avons une grammaire G1 (L) de type 0 et une grammaire
G2 (L) de type 1. Donc, L est un langage de type 1 (voir 1.1.3).

5.3 Machines de Turing

Pour reconnaitre les mots des langages de type 0, on utilise des machines de Turing.

55 [Link]
 CHAPITRE 5. LANGAGES RÉCURSIVEMENT ÉNUMÉRABLES ET CALCULABILITÉ

5.3.1 Composition d’une Machine de Turing

Les composants d’une machine de Turing sont :

Une bande de lecture/écriture infinie : La bande de lecture d’une machine de
Turing est aussi une bande d’écriture. Chaque case pouvant contenir un seul
symbole de l’alphabet d’entrée ou de l’alphabet auxiliaire d’écriture. Cette bande
est infinie.
Une tête de lecture/écriture : La tête de lecture peut lire une case à un instant
donné mais aussi écrire dans une case. La tête peut être déplacée par l’automate
pour se positionner sur la case immédiatement à gauche ou à droite de la case
courante.
Une unité de contrôle : Elle est définie par un ensemble fini d’états ainsi que par
une fonction de transition qui décrit le passage d’un état à un autre en fonction
du contenu de la case courante de la bande de lecture et de l’état dans lequel se
trouve la machine de Turing. L’unité de contrôle décide aussi de la direction dans
laquelle il faut déplacer la tête de lecture/écriture.
Avant même l’apparition des premiers ordinateurs, Alain Turing (1912 - 1954), un
mathématicien et cryptographe britannique a proposé un modèle théorique en la ma-
chine de Turing en 1936 qui est une abstraction des ordinateurs modernes. Le micro-
processeur est représenté par l’unité de contrôle, le nombre d’états, étant fini, peut être
assimilé au nombre de configurations fini des microprocesseurs. Les mémoires (registres,
mémoire vive et disques dures) représentées par une bande de lecture/écriture infinie.
A noter que quel que soit le nombre et la taille des mémoires, on ne pourra jamais avoir
une mémoire infinie.

5.3.2 Définition formelle d’une Machine de Turing

Une machine de Turing M T est un sextuplet AP = (A, X, Q, e0 , ef , δ) :

A est l’alphabet des mots en entrée : C’est l’alphabet du langage des mots à
reconnaitre.
X est l’alphabet auxiliaire d’écriture : C’est les symboles qui sont utilisés pour
le marquage.
Q est un ensemble non vide d’états : Utilisé entre autre pour déterminer à quel
étape se trouve la machine de Turing dans la reconnaissance des mots.
e0 ∈ Q est l’état initial : État par lequel la machine de Turing commence la re-
connaissance.
ef ∈ Q est un état final : Il y a la possibilité d’utiliser un seul état final dans
machine de Turing.
δ est un ensemble de transitions : Les transitions permettent de faire certaines
actions à la lecture d’un symbole, comme par exemple le changement d’état,
l’écriture ou le changement de direction de la tête de lecture/écriture.

56 [Link]
 CHAPITRE 5. LANGAGES RÉCURSIVEMENT ÉNUMÉRABLES ET CALCULABILITÉ

5.3.3 Représentation des Machines de Turing

Concernant les machines de Turing, nous allons utiliser uniquement la représentation

tabulaire qui est comme suit :
— Chaque ligne représente un état.
— Chaque colonne représente un symbole de l’alphabet du langage ou de l’alphabet
auxiliaire.
— L’état initial est marqué par une flèche entrante et l’état final par une flèche
sortante.
— Les cases du tableau sont constituées de triplets (état destination, le symbole
écrit, la direction). La direction est soit D pour droite ou G pour gauche.

5.3.4 Utilisations des Machines de Turing

On utilise les machines de Turing pour faire :

— la reconnaissance,
— la génération,
— le calcul.

5.3.5 Différence entre la reconnaissance avec les machines de Turing et la

reconnaissance avec les machines de Turing à bornes linéaires

Dans une machine de Turing à bornes linéaires, le marquage qui est utilisé pour la
reconnaissance doit être réalisé en utilisant l’espace du mot (entre les deux symboles ]).
Si l’espace du mot n’est pas suffisant pour décider si un mot appartient à un langage
donné L et qu’il est nécessaire de faire un calcul qui prend plus d’espace que la taille
du mot, alors L n’est pas un langage de type 1 mais de type 0. Car, la bande de
lecture/écriture d’une machine de Turing n’est pas limitée, elle contient un mot ou
plusieurs mots séparés par une case vide entre tout couple de mots. Les autres cases sont
vides. La case vide est représentée par un  . Du coup, pour reconnaitre un mot, la
machine de Turing peut utiliser les cases vides pour faire un marquage supplémentaire.
C’est ce qui permet de faire des calculs.

Par exemple pour le langage : L = {m/m ∈ 1(0∗ 1∗ )∗ ∪ 0 et la valeur entière de m

représentée en binaire est divisible par 3} Pour savoir si un mot appartient à L, on
doit déterminer si ce mot écrit en binaire est divisible par 3, ce qui n’est pas possible
directement. On doit écrire m d’une certaine façon qui nous permet de savoir s’il est
divisible par 3 ou pas. On a donc besoin de plus d’espace que l’espace réservé au mot
m écrit en binaire pour décider si m appartient au langage. Pour résoudre ce problème
on doit utiliser la calculabilité.

57 [Link]
 CHAPITRE 5. LANGAGES RÉCURSIVEMENT ÉNUMÉRABLES ET CALCULABILITÉ

5.4 Calculabilité

La calculabilité est l’utilisation d’une machine de Turing pour le calcul. Les nombres
positifs ou nul peuvent être représenté à l’aide du symbole  | .

exemple de nombres sur une machine de Turing

— 0: |
— 1: ||
— 2: |||
— 3: ||||
— 4: |||||
— 5: ||||||
— ...

5.4.1 Procédure de calcul dans les Machines de Turing

Initialement, la tête de lecture/écriture est positionné sur le premier | du premier nombre

(les nombres étant positifs ou nul, on a au moins un | par nombre). les nombres sont
séparés par une case vide. Il existe aussi une case vide entre le dernier nombre et le
résultat. La case vide est représentée par un  . A la fin de la procédure de calcul,
la machine de Turing doit être sur l’état final et la tête de lecture doit être positionné
sur le premier | du résultat.

5.4.2 exemple

On souhaite calculer a + b.
La bande de lecture/écriture contient alors deux nombres séparés par une case vide et
le reste de la bande (qui est infinie) est vide.
Si a = 3 et b = 1, on aura donc ... |||| || ...
Le résultat doit se trouver après les deux nombres a et a et une case vide.
Si a = 3 et b = 1 alors a + b = 4, on aura donc ...| |||| ...
L’idée est d’abord de marquer le premier | de chaque nombre et de mettre un premier
symbole | dans la partie résultat qui représente le 0. Ensuite, il suffit qu’à chaque fois
qu’on marque un symbole | de a ou de b, on rajoute un symbole | au résultat. Ce qui
donne la machine de Turing suivante :

58 [Link]
 CHAPITRE 5. LANGAGES RÉCURSIVEMENT ÉNUMÉRABLES ET CALCULABILITÉ

| X
→ e0 (e1 , X, D)
e1 (e1 , |, D) (e2 , , D)
e2 (e3 , X, D) (e6 , , G)
e3 (e3 , |, D) (e4 , , D)
e4 (e4 , |, D) (e5 , |, G)
e5 (e5 , |, G) (e2 , X, D) (e5 , , G)
e6 (e6 , X, G) (e7 , , G)
e7 (e7 , |, G) (e8 , X, D)
e8 (e9 , X, D) (e11 , , D)
e9 (e9 , |, D) (e10 , , D)
e10 (e10 , X, D) (e4 , , D)
e11 (e11 , X, D) (ef , , D)
← ef
Exemple avec a = 3 et b = 1 : on a donc sur la bande lecture ... |||| || ...
Initialement la machine de Turing se trouve à l’état initial e0 et la tête de lecture/écriture
sur le premier | du nombre a. Il existe une transition qui va de cette configuration vers
l’état e1 avec le marquage du symbole | avec le symbole X et la tête de lecture/écriture
se déplace à droite(... X ||| || ...).
L’état e1 est utilisé pour passer tous les autres symboles | sans les marquer jusqu’à ce
que la tête de lecture se trouve sur le vide alors la machine de Turing passe à l’état e2 .
La machine de Turing se trouve alors à l’état e2 et la tête de lecture/écriture sur le
premier | du nombre b. Il existe une transition qui va de cette configuration vers l’état
e3 avec le marquage du symbole | avec le symbole X et la tête de lecture/écriture se
déplace à droite(... X ||| X | ...).
L’état e3 est utilisé pour passer tous les autres symboles | sans les marquer jusqu’à ce
que la tête de lecture se trouve sur le vide alors la machine de Turing passe à l’état e4 .
La machine de Turing se trouve alors à l’état e4 et la tête de lecture/écriture après les
deux nombres et un vide |. Il existe une transition qui va de cette configuration vers
l’état e5 avec le marquage du vide avec le symbole | et la tête de lecture/écriture se
déplace à gauche (... X ||| X | | ...).
La suite des marquages va se dérouler comme suit :
— ... X ||| XX | ...
— ... X ||| XX || ...
— ... XX || XX || ...
— ... XX || XX ||| ...
— ... XXX | XX ||| ...
— ... XXX | XX |||| ...
— ... XXXX XX |||| ...
— ... XXXX XX ||||| ...
A ce moment, la machine de Turing ne peut plus marquer de symbole |. Elle va se
positionner sur le premier symbole du résultat et sur l’état final. Le calcul est terminer.

59 [Link]
 CHAPITRE 5. LANGAGES RÉCURSIVEMENT ÉNUMÉRABLES ET CALCULABILITÉ

5.5 Conclusion

Les langages récursivement énumérables sont le dernier type de langages qu’on a abordé
dans cette matière. Ils sont générés par des grammaires sans restriction et les mots d’un
langage récursivement énumérables peuvent être reconnus par une machine de Turing.
Les machines de Turing peuvent être utilisées pour la reconnaissance, la génération et
le calcul. C’est cette dernière fonction qui nous a particulièrement intéressé dans ce
chapitre.

60 [Link]
 CHAPITRE 5. LANGAGES RÉCURSIVEMENT ÉNUMÉRABLES ET CALCULABILITÉ

5.6 Exercices

Exercice 1 : Faire une machine de Turing qui calcule :

1. | a − b | avec a et b des entiers positifs ou nuls.
2. a ∗ b avec a et b des entiers positifs ou nuls.

61 [Link]
Chapitre 6

Corrigés d’exercices

Corrigés des exercices du chapitre 1

Corrigé de l’exercice 1 :
1. uv = 11100
u3 = 111111
u2 v 2 = 1111100100
(uv)2 = 1110011100
2. E1 = {000, 001, 010, 011, 100, 101, 110, 111}
3. E2 = {ε, 00, 01, 10, 11, 0000, 0001, 0010, 0011, 0100,0101,0110,0111,1000, 1001, 1010,
1011, 1100, 1101, 1110, 1111}
4. E3 = {000, 001, 011, 100, 110, 111}
5. L1L2 = 01+ 10+ = 011+ 0+
(L2)∗ L1 = (10+ )∗ 01+
L1 ∪ C(L1 ∩ L2) = L1 ∪ C(∅) = L1 ∪ A∗ = A∗

Corrigé de l’exercice 2 :
1. L1 = a(a∗ b∗ c∗ )∗
2. L2 = (a∗ b∗ c∗ )∗ a
3. L3 = (a∗ b∗ c∗ )∗ a(a∗ b∗ c∗ )∗
4. L4 = (a∗ b∗ c∗ )∗ aab(a∗ b∗ c∗ )∗ aab(a∗ b∗ c∗ )∗
5. L5 = C(L1)

Corrigé de l’exercice 3 :
1. c)
2. b)c)d)
3. a)b)
4. c)

62
 CHAPITRE 6. CORRIGÉS D’EXERCICES

Corrigé de l’exercice 4 : .
.

63 [Link]
 CHAPITRE 6. CORRIGÉS D’EXERCICES

Corrigés des exercices du chapitre 2

Corrigé de l’exercice 1 : .

Gd (L1) est une grammaire régulière à droite de L1 :

Gd (L1) = (T, Nd , Sd , Rd )
T = {a, b}
Nd = {Sd , Sd0 }
Rd = {
Sd → aSd /aSd0 ,
Sd0 → bSd0 /b
}
Gg (L1) est une grammaire régulière à gauche de L1 :
Gg (L1) = (T, Ng , Sg , Rg )
T = {a, b}
Ng = {Sg , Sg0 }
Rg = {
Sg → Sg b/Sg0 b/,
Sg0 → Sg0 a/a
}

Figure 6.1: AEF(L1)

Corrigé de l’exercice 2 :

1. L = a∗ b∗ c∗
2. L = (a∗ b∗ )∗
3. L = a∗ (b+ cb ∪ c∗ abc)
4. L = [a∗ (ba ∪ bbc+ ∪ cc+ )]∗ c

64 [Link]
 CHAPITRE 6. CORRIGÉS D’EXERCICES

Corrigé de l’exercice 4 : .
On remarque d’abord que e7 est un état inaccessible. Il faut donc le supprimer.
Passant maintenant à la représentation tabulaire de l’automate.
a b
→ e0 {e1 , e4 } e1
e1 e4 {e1 , e2 }
e2 - e1
e3 - e5
e4 {e3 , e6 } -
e5 - -
← e6 e8 {e5 , e6 }
e8 - -

Table 6.1: La représentation tabulaire de l’AEF

On remarque que l’automate est indéterministe. Il faut donc le rendre déterministe puis
complet.
a b
→ e0d = e0 e2d e2d
e1d = {e1 , e4 } e3d e4d
e2d = e1 e5d e4d
e3d = {e3 , e4 , e6 } e6d e7d
e4d = {e1 , e2 } e5d e4d
e5d = e4 e8d ep
← e6d = {e3 , e6 , e8 } e9d e7d
← e7d = {e5 , e6 } e9d e7d
← e8d = {e3 , e6 } e9d e7d
e9d = e8 ep ep
ep ep ep

Table 6.2: La représentation tabulaire de l’AEF déterministe et complet

On peut alors commencer le déroulement de l’algorithme de minimisation.

— G1 = {e6d , e7d , e8d },G2 = {e0d , e1d , e2d , e3d , e4d , e5d , e9d , ep }
— G1 = {e6d , e7d , e8d }, G2 1 = {e0d , e1d , e2d , e4d , e9d , ep }, G2 2 = {e3d }, G2 3 = {e5d }
— G1 = {e6d , e7d , e8d }, G2 1 1 = {e0d , e9d , ep }, G2 1 2 = {e1d , e2d , e4d , e5d , ep },
G2 1 3 = {e2d , e4d }, G2 2 = {e3d }, G2 3 = {e5d }
— G1 = {e6d , e7d , e8d }, G2 1 1 1 = {e0d }, G2 1 1 2 = {e9d , ep }, G2 1 2 = {e1d },
G2 1 3 = {e2d , e4d }, G2 2 = {e3d }, G2 3 = {e5d }
On obtient alors l’automate à états finis suivant :
AEF (L) = {A, Q, I, F, δ)
A = {a, b}

65 [Link]
 CHAPITRE 6. CORRIGÉS D’EXERCICES

Q = {G1, G2 1 1 1, G2 1 1 2, G2 1 2, G2 1 3, G2 2, G2 3}
I = {G2 1 1 1}
F = {G1}
δ={
(G2 1 1 1 a) → (G2 1 2),
(G2 1 1 1 b) → (G2 1 3),
(G2 1 2, a) → (G2 2),
(G2 1 2, b) → (G2 1 2),
(G2 1 3, a) → (G2 3),
(G2 1 3, b) → (G2 1 3),
(G2 2, a) → (G1),
(G2 2, b) → (G1),
(G2 3, a) → (G2 1 1 2),
(G2 3, b) → (G2 1 1 2),
(G1, a) → (G2 1 1 2),
(G1, b) → (G1),
(G2 1 1 2, a) → (G2 1 1 2),
(G2 1 1 2, b) → (G2 1 1 2),
}

66 [Link]
 CHAPITRE 6. CORRIGÉS D’EXERCICES

Corrigés des exercices du chapitre 3

Corrigé de l’exercice 1 : .

G(L1) = (T, N, S, R)
T = {a, b, c, d}
N = {S, S 0 , S 00 }
R={
S → S 0 S 00 ,
S 0 → aS 0 b/ab,
S 00 → cS 00 d/cd
}

AP (L1) = (A, P, Q, e0 , F, δ)
A = {a, b, c, d}
P = {a, c}
Q = {e0 , e1 , e2 }
F = {e2 }
δ={
(e0 , a, ε) → (e0 , a),
(e0 , a, a) → (e0 , aa),
(e0 , b, a) → (e1 , ε),
(e1 , b, a) → (e1 , ε),
(e1 , c, ε) → (e1 , c),
(e1 , c, c) → (e1 , cc),
(e1 , d, c) → (e2 , ε),
(e2 , d, c) → (e2 , ε)
}

G(L2) = (T, N, S, R)
T = {a, b, c, d}
N = {S, S 0 }
R={
S → aSd/aS 0 d
S 0 → bS 0 c/bc
}

AP (L2) = (A, P, Q, e0 , F, δ)
A = {a, b, c, d}
P = {a, b}
Q = {e0 , e1 }
F = {e1 }
δ={

67 [Link]
 CHAPITRE 6. CORRIGÉS D’EXERCICES

(e0 , a, ε) → (e0 , a),

(e0 , a, a) → (e0 , aa),
(e0 , b, a) → (e0 , ab),
(e0 , b, b) → (e0 , bb)
(e0 , c, b) → (e1 , ε),
(e1 , c, b) → (e1 , ε),
(e1 , d, a) → (e1 , ε)
}

Corrigé de l’exercice 2 : .

L1 = {mcmr /m ∈ (a∗ b∗ )∗ }
L2 = {m/m ∈ (a∗ b∗ )∗ (c∗ d∗ )∗ et | m |a =| m |b et | m |c =| m |d }

G(L1) = (T, N, S, R)
T = {a, b, c}
N = {S}
R = {S → aSa/bSb/c}

AP (L1) = (A, P, Q, e0 , F, δ)
A = {a, b, c}
P = {a, b}
Q = {e0 , e1 }
F = {e1 }
δ={
(e0 , a, ε) → (e0 , a),
(e0 , a, a) → (e0 , aa),
(e0 , a, b) → (e0 , ba)
(e0 , b, ε) → (e0 , b)
(e0 , b, a) → (e0 , ab),
(e0 , b, b) → (e0 , bb)
(e0 , c, ε) → (e1 , ε),
(e0 , c, a) → (e1 , a),
(e0 , c, b) → (e1 , b),
(e1 , b, b) → (e1 , ε),
(e1 , a, a) → (e1 , ε)
}

G(L2) = (T, N, S, R)
T = {a, b, c, d}
N = {S, S 0 , S 00 }
R={

68 [Link]
 CHAPITRE 6. CORRIGÉS D’EXERCICES

S → S 0 S 00 ,
S 0 → aS 0 bS 0 /bS 0 aS 0 /ε,
S 00 → cS 00 dS 00 /dS 00 cS 00 /ε
}

AP (L2) = (A, P, Q, e0 , F, δ)
A = {a, b, c, d}
P = {a, b, c, d}
Q = {e0 , e1 }
F = {e0 , e1 }
δ={
(e0 , a, ε) → (e0 , a),
(e0 , a, a) → (e0 , aa),
(e0 , b, a) → (e0 , ε),
(e0 , b, ε) → (e0 , b),
(e0 , b, b) → (e0 , bb),
(e0 , a, b) → (e0 , ε),
(e0 , c, ε) → (e1 , c),
(e0 , d, ε) → (e1 , d),
(e1 , c, c) → (e1 , cc),
(e1 , c, ε) → (e1 , c),
(e1 , c, d) → (e1 , ε),
(e1 , d, c) → (e1 , ε),
(e1 , d, d) → (e1 , dd)
(e1 , d, ε) → (e1 , d)
}

Corrigé de l’exercice 4 :
1. a)b)c)d)
2. b)
3. a)
4. a)
5. b)

69 [Link]
 CHAPITRE 6. CORRIGÉS D’EXERCICES

Corrigés des exercices du chapitre 4

Corrigé de l’exercice 1 : .
3n 2n n
L2 = {a b c , n > 0}
a b c A B C ]
→ e0 (e1 , A, D) (e7 , B, D)
→ e1 (e2 , A, D)
→ e2 (e3 , A, D)
e3 (e3 , a, D) (e4 , B, D) (e3 , B, D)
e4 (e5 , B, D)
e5 (e5 , b, D) (e6 , C, G) (e5 , C, D)
e6 (e6 , a, G) (e6 , b, G) (e0 , A, D) (e6 , B, G) (e6 , C, G)
e7 (e7 , B, D) (e7 , C, D) (ef , ], D)
← ef
n
L3 = {a2 , n ≥ 0}
a A ]
→ e0 (e1 , A, D) (e0 , A, D)
e1 (e2 , a, D) (e1 , A, D) (ef , ], D)
e2 (e3 , A, D) (e2 , A, D) (e4 , ], G)
e3 (e2 , A, D) (e3 , A, D)
e4 (e4 , A, G) (e4 , A, G) (e0 , ], D)
← ef

70 [Link]
 CHAPITRE 6. CORRIGÉS D’EXERCICES

Corrigés des exercices du chapitre 5

Corrigé de l’exercice 1 :
1. | a − b | avec a et b des entiers positifs ou nuls.
| X
→ e0 (e1 , X, D)
e1 (e1 , |, D) (e2 , X, D)
e2 (e3 , X, D)
e3 (e3 , |, D) (e4 , , D)
e4 (e4 , |, D) (e5 , |, G)
e5 (e5 , |, G) (e6 , , G)
e6 (e6 , |, G) (e6 , X, G) (e7 , , D)
e7 (e8 , X, D) (e7 , X, D) (ef , , D)
e8 (e8 , |, D) (e9 , X, D) (e4 , , D)
e9 (e6 , X, G) (e9 , X, D) (e4 , , D)
← ef

71 [Link]
Bibliographie

[1] A. V. Aho and J. D. Ullman. Principles of Compiler Design. Addison-Wesley, 1977.

[2] J-M. Autebert. Théorie des langages et des automates. MASSON, 1994.
[3] O. Carton. Langages formels, Calculabilité et complexité. Vuibert, 2014.
[4] M. Noureddine. Théorie des langages. Office des publications universitaires, 1991.

72