Curriculum LDD Informatique-Mathématiques

Cours : Langages Formels (S2)

Objectifs : Ce cours étudie les familles de langages rationnels et algébriques, des concepts essentiels de l'informatique fondamentale. Entre autres, nous présentons différentes caractérisations de ces langages en termes d'automates, d'expressions régulières, de grammaires, de monoïdes et de logique. Une application majeure étant l'analyse lexicale et syntaxique dans la construction des compilateurs, nous en étudierons les bases théoriques et les mettrons en pratique à travers un projet.

Plan détaillé :

  1. Mots, langages et leurs opérations
  2. Automates finis déterministes et non-déterministes, déterminisation, propriétés de clôture, lemme de l'étoile
  3. Résiduels, minimisation
  4. Monoïde syntaxique
  5. Expressions rationnelles
  6. Grammaires, hiérarchie de Chomsky
  7. Logique monadique du second ordre
  8. Automates à pile et grammaires algébriques, lemme d'itération
  9. Calculs d'accessibilité, automates à pile réguliers
  10. Langages déterministes, propriétés de clôture
  11. Analyse lexicale et syntaxique (SLR, LR, LALR)
  12. Problèmes décidables et indécidables
  13. Automates à pile visible

Références :

  • Olivier Carton. Langages formels, calculabilité et complexité. Vuibert, 2008
  • John E. Hopcroft, Rajeev Motwani et Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation. 3e éd. Pearson, 2006.
  • Dexter C. Kozen. Automata and Computability. Springer, 1997.
  • Jacques Sakarovitch. Éléments de théorie des automates. Vuibert, 2003.