L'objectif de ce cours consiste à montrer l'intérêt et l'utilité des automates en tant que modèles comportementaux et surtout en tant que structures de données/outils algorithmiques. Pour les situations où les automates finis sur les mots finis (que vous connaissez déjà bien) ne suffisent pas, nous présenterons les variantes utiles des automates, étudierons leurs propriétés de base et montrerons leurs applications. Nous revisiterons également les langages algébriques, grammaires hors contexte et automates à pile.

Dans ce cours nous privilégions la couverture à la profondeur. Nous souhaitons que chaque étudiant(e) acquière les bonnes intuitions concernant les applications des automates, qu'il (elle) ait un arsenal des outils basés sur les automates. Il s’agit d’un cours d’informatique fondamentale, avec des théorèmes, des raisonnements et des algorithmes intéressants.

• Introduction et révisions (automates finis et langages réguliers)
• Apprentissage automatique des langages réguliers
• Application 1: BDD - diagrammes de décision binaires (représentation de fonctions booléennes)
• Application 2 : procédure de décision de l'arithmétique de Presburger
• Grammaires et hiérarchie de Chomsky
• Langages hors contexte
• Automates à pile
• Mots infinis et ω-langages
• Automates cellulaires