Préparation en langages formels
Notes de révision
Voici des notes de révision, sur la première partie du programme (langages rationnels). Il y aura peut-être une suite sur les langages algébriques, un jour...
Contenu
Issu du rapport officiel.
Programme
- Automates finis. Langages reconnaissables. Lemme d'itération.
Existence de langages non reconnaissables. Automates complets. Automates
déterministes. Algorithme de déterminisation. Propriétés de
clôture des langages reconnaissables.
- Expressions rationnelles. Langages rationnels. Théorème de
Kleene.
- Automate minimal. Résiduel d'un langage par un mot. Algorithme de
minimisation.
- Utilisation des automates finis : recherche de motifs, analyse
lexicale.
- Langages algébriques. Lemme d'Ogden. Existence de langages non algébriques. Grammaires algébriques. Propriétés de clôture des langages algébriques.
- Automates à pile. Langages reconnaissables par automates à
pile.
- Utilisation des automates à pile : analyse syntaxique. Grammaires
LL(1).
Leçons
- Leçon 908
- Automates finis. Exemples et applications.
- Leçon 909
- Langages rationnels. Exemples et applications.
- Leçon 910
- Langages algébriques. Exemples et applications.
- Leçon 911
- Automates à pile. Exemples et applications.
- Leçon 923
- Analyses lexicale et syntaxique : applications.
- Leçon 907
- Algorithmique du texte : exemples et applications.
Feuilles d'exercices
Pour s'exercer chez soi, et pour des exemples de développements. Voir aussi les feuilles de TD du cours de langages formels.
- Automates finis
- Langages rationnels
- Lemmes d'itération
- Minimisation
- Grammaires algébriques
- Automates à pile
- Encore des automates à pile
Bibliographie
Quelques ouvrages recommandés pour préparer vos leçons et développements. Certains font partie de la bibliothèque de l'agrégation ([Sak03], [Aut94] et une édition plus récente de [HU79]), et la plupart devront être dans la malle de la préparation de Cachan ([Sak03], [Car08], [Aut94], [ASU86], [GBJL00] et deux éditions, l'une plus ancienne, l'autre plus récente de [HU79]).
Automates finis, langages rationnels
- [Sak03]
- Jacques Sakarovitch. Éléments de théorie des automates. Vuibert, 2003.
Langages algébriques
- [Har78]
- Michael A. Harrison. Introduction to Formal Language Theory. Addison Wesley, 1978.
En général
- [Car08]
- Olivier Carton. Langages formels, calculabilité et complexité. Vuibert, 2008.
- [HU79]
- John E. Hopcroft et Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison Wesley, 1979.
- [Aut94]
- Jean-Michel Autebert. Théorie des langages et des automates. Masson, 1994.
Analyse lexicale et syntaxique
- [GBJL00]
-
Dick Grune, Henri E. Bals, Ceriel J.H. Jacobs et Koen
G. Langendoen.
Compilateurs.
Dunod, 2002.
Traduit de Modern Compiler Design, John Wiley & Sons, 2000.
- [ASU86]
- Alfred Aho, Ravi Sethi et Jeffrey Ullman.
Compilateurs: Principes, techniques et outils.
Dunod, 2000.
Traduit de Compilers, Addison Wesley, 1986.
- [SSS88]
- Seppo Sippu et Eljas Soisalon-Soininen.
Parsing Theory, Vol. I: Languages and Parsing.
EATCS Monographs on Theoretical Computer Science volume 15,
Springer, 1988.
- [SSS90]
- Seppo Sippu et Eljas Soisalon-Soininen.
Parsing Theory, Vol. II: LR(k) and LL(k) Parsing.
EATCS Monographs on Theoretical Computer Science volume 20,
Springer, 1990.