Automates et langages

Programme résumé : Langages réguliers et automates d'états finis

* Thème 0 : Définition inductive et preuve par induction
o Théorème de Kleene et points fixes
o Schéma de preuve par induction

o Reconnaissance d'un langage régulier par un automate d'états fini
o Propriétés algébriques des langages réguliers
o Notion de non déterminisme, déterminisation d'un automate
o Problèmes de décision : langage vide, langage infini

Compétences visées : 

La maîtrise de la programmation s'appuie sur l'étude des langages et moyens d'expression utilisés en informatique et sur la compréhension des modèles de calcul sous-jacents.
Les automates sont des structures finies qui permettent de décrire des phénomènes infinis, par exemple l'ensemble des comportements d´un programme ou l'ensemble des phrases d'un langage. 
La théorie des automates fait partie des fondements de l'informatique. Dans ce cours nous l'abordons avec les objectifs suivants :
* Apprendre à analyser des propriétés (correction, terminaison, coût) des algorithmes (en relation avec l'UE INF231)
* Apprendre à analyser formellement les propriétés d'un langage