Préface iii
Avant-propos v
1 Langages 1
1 Symbole 2
2 Alphabet 2
3 Mot 3
3.1 Opérations de base sur les mots 3
4 Langages 7
4.1 Opérations sur les langages 8
5 Trois questions fondamentales 11
6 Exercices avec solutions 13
2 Grammaires formelles 15
1 Introduction 16
2 Grammaire formelle 17
3 Dérivation 19
4 Langage engendré par une grammaire 21
4.1 Équivalence de deux grammaires 22
5 Classification de Chomsky 23
5.1 Grammaire générale 23
5.2 Grammaire de type 1 24
5.3 Grammaire hors-contexte 27
5.4 Grammaire régulière 27
5.5 Le mot vide 28
6 Notion d’automate
7 Exercices avec solutions 31
3 Langages réguliers 35
1 Grammaires régulières 37
2 Automates finis 38
2.1 Automates finis déterministes 39
2.1.1 Configuration et dérivation 40
2.1.2 Langage accepté par un automate fini 42
2.1.3 Représentations d’un automate fini 44
2.1.4 Automates équivalents et automates complets 46
2.2 Automates finis non-déterministes 48
2.3 Déterminisation d’automates finis 52
2.3.1 Élimination des ε-transitions 58
2.4 Minimisation d’automates finis 61
2.4.1 Indistinguabilité 62
2.4.2 Congruence de Nerode 64
2.4.3 Classe d’équivalence 65
2.4.4 Automate quotient 65
2.4.5 Congruence pour des mots 66
2.4.6 Algorithme de Moore 67
3 Automates finis et grammaires régulières 71
3.1 Grammaire régulière à partir d’un automate fini 71
3.2 Automate fini à partir d’une grammaire régulière 72
4 Propriétés des langages réguliers 74
4.1 Propriétés ensemblistes des langages réguliers 74
4.2 Lemme de pompage pour les langages réguliers 81
4.3 Problèmes de décision 85
5 Expressions régulières 87
5.1 Définitions 88
5.2 Propriétés algébriques 89
6 Automates finis et expressions régulières 90
6.1 Automate fini à partir d’une expression régulière 91
6.2 Expression régulière à partir d’un automate fini 97
6.2.1 Méthode de Brzozowsky et McCluskey 97
6.2.2 Méthode des équations 101
7 Exercices avec solutions 108
8 Projet de programmation en langage C
4 Langages hors-contexte 115
1 Grammaires hors-contexte 117
1.1 Dérivations 119
1.2 Arbres de dérivation 120
1.3 Ambiguïté 123
2 Propriétés des langages hors-contexte 131
2.1 Propriétés ensemblistes des langages hors-contexte 131
2.2 Lemme de pompage pour les langages hors-contexte 133
2.3 Problèmes de décision 134
3 Transformations des grammaires hors-contexte 135
3.1 Grammaires réduites 136
3.1.1 Élimination des symboles non productifs 136
3.1.2 Élimination des symboles inaccessibles 138
3.2 Grammaires propres 140
3.2.1 Élimination des règles vides 141
3.2.2 Élimination des règles unitaires 144
3.3 Grammaires récursives à gauche 146
3.4 Forme normale de Chomsky 151
3.5 Forme normale de Greibach 153
4 Automates à pile 155
4.1 Configuration et calcul d’un automate à pile 158
4.2 Langage accepté par un automate à pile 160
4.3 Déterminisme versus non-déterminisme 163
5 Automates à pile et grammaires hors-contexte 166
5.1 Automate à pile à partir d’une grammaire hors-contexte 167
6 Exercices avec solutions 169
5 Langages récursivement énumérables 171
1 Grammaires générales 173
2 Machine de Turing 176
2.1 Configuration et calcul d’une machine de Turing 179
2.2 Langage accepté par une machine de Turing 181
3 Langages récursivement énumérables 184
3.1 Langages récursifs 184
3.2 Langages récursivement énumérables 185
3.3 Discussion 185
4 Déterminisme versus non-déterminisme
5 Machine de Turing comme calculateur 186
6 Exercices avec solutions 188
Annexes 191
A Solutions des exercices 193
A.1 Chapitre 1 193
A.2 Chapitre 2 195
A.3 Chapitre 3 199
A.4 Chapitre 4 209
A.5 Chapitre 5 217
B Examens finaux 222
B.1 Examen final n°1 222
B.2 Examen final n°2 224
B.3 Examen final n°3 226
B.4 Examen final n°4 228
B.5 Examen final n°5 229
C Corrigés des examens finaux 231
C.1 Corrigé de l’examen final n°1 231
C.2 Corrigé de l’examen final n°2 235
C.3 Corrigé de l’examen final n°3 239
C.4 Corrigé de l’examen final n°4 242
C.5 Corrigé de l’examen final n°5 245
D Exercices non corrigés 248
D.1 Chapitre 1 248
D.2 Chapitre 2 249
D.3 Chapitre 3 251
D.4 Chapitre 4 257
D.5 Chapitre 5 261
Bibliographie 263
Index
