Automates et Théorie des Langages (cours 2SN - BML - ENSEEIHT)

Contenus du cours

1. Automates finis, Composition d’Automates, Automates hiérarchiques

   • Introduction à la modélisation de systèmes à base d’états (notion de systèmes états transitions)
   • Théorie des langages, Automates finis indéterministes/déterministes,
   • Déterminisation et minimisation des automates
   • TD 1 : Modélisation avec automates finis, Déterminisation

2. Rappels sur les langages (alphabet, mot, expressions régulières); langages associés aux expressions régulières; suite sur les automates: déterminisation et minimisation

   • TD 2 : Preuve d’équivalence, Déterminisation

3. Équivalence : Automates finis, Expressions régulières, Grammaires régulières à droite

   • TD 3 : Equivalence : Automates finis, Expressions régulières, Grammaires régulières à droite

4. Automates à piles, Indéterminisme, Equivalence grammaires algébriques, Analyse descendante récursive

   • Éléments sur les langages context-free; notion de premiers, suivants, symboles directeurs, analyse descendante récursive, …
   • TD 4 : Automates à piles, Analyse descendante récursive

5. Machine de Turing, Introduction à la Calculabilité et la Complexité