Préparation en langages formels

Préparation à la leçon d'informatique de l'agrégation de mathématiques, option D, sur le thème des langages formels. Animée par Sylvain Schmitz.

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

  1. 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.
  2. Expressions rationnelles. Langages rationnels. Théorème de Kleene.
  3. Automate minimal. Résiduel d'un langage par un mot. Algorithme de minimisation.
  4. Utilisation des automates finis : recherche de motifs, analyse lexicale.
  5. 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.
  6. Automates à pile. Langages reconnaissables par automates à pile.
  7. 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.

  1. Automates finis
  2. Langages rationnels
  3. Lemmes d'itération
  4. Minimisation
  5. Grammaires algébriques
  6. Automates à pile
  7. 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.

Liens utiles