Fondements 1 : langages formels, automates et calculabilité

Bibliographie

• Dominique Perrin, « Les débuts de la théorie des automates », dans Technique et science informatiques, 1995.
• Olivier Carton, Langages formels, calculabilité et complexité, Vuibert, 2008.
• Jacques Sakarovitch, Éléments de théorie des automates, Vuibert, 2003.
• John E. Hopcroft, Rajeev Motwani, et Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Prentice Hall, 2007.
• Jean-Michel Autebert, Théorie des langages et des automates, Masson, 1994.
• Pierre Wolper, Introduction à la calculabilité, Dunod, 2006.

Contenu

1. Mots et langages
2. Langages réguliers, langages rationnels
3. Automates finis, déterminisation et minimisation
4. Lemmes de l'étoile pour les langages reconnaissables
5. Problèmes de décision sur les langages reconnaissables
6. Applications à la logique, l'algèbre et l'arithmétique
7. Grammaires et langages algébriques
8. Lemmes de l'étoile pour les langages algébriques
9. Formes normales de grammaires
10. Automates à pile
11. Langages déterministes et analyse syntaxique
12. Problèmes de décision sur les langages algébriques
13. Introduction à la calculabilité - Fonctions µ-récursives.
14. Machines de Turing - Extensions - Équivalence avec les fonctions µ-récursives.
15. Non-calculabilité.

TD

Les TD sur la partie langages formels et les cours sur la partie calculabilité sont assurés par Gilles Lesventes.

Examens

• Le sujet d'examen de l'année 2012-2013.
• Le sujet d'examen de l'année 2013-2014.