Syllabus 2013/2014
 
Extrait PDF Anglais
Français
index
Module : IF114
Titre :
Automates finis et applications
Volumes horaires :
Cours Intégré : 16.00 h
Travail Individuel : 12.00 h
Crédits ECTS :
1.50
Évaluation :
S1: ET(2h,E,fa,sc) x0.6 + CC x0.4; S2: ET(2h,E,fa,sc) x0.6 + rep(CC S1) x0.4   Détail de la nomenclature employée pour la création du code d'évaluation
Enseignant(s) :
HERBRETEAU Frédéric - Responsable
SAHEB Nasser
CASADEI Astrid
LOMBARDY Sylvain
Partagé par l'UE (les UEs) :
Niveau :
module de première année
Résumé :
Les automates finis permettent de modéliser des programmes informatiques à mémoire finie. Ils permettent de résoudre des problèmes à un niveau d'abstraction élevé, sans s'encombrer des spécificités d'un langage donné, et en se concentrant sur les invariants à maintenir pour parvenir à une solution. L'étude de ce modèle s'inscrit dans le cadre général de la théorie des langages abordée ensuite dans les modules IF203 (compilation) et IF228 (calculabilité et complexité). L'enseignement aborde des notions théoriques (automates finis, langages réguliers, expressions régulières, équivalence de ces trois formalismes, non-déterminisme, automate minimal, lemme de l'étoile) ainsi que leur utilisation pour la résolution de problèmes concrets.
Plan :
  1. Automates finis, langages
  2. Expressions régulières, théorème de Kleene
  3. Langages non-réguliers, lemme de l'étoile
  4. Déterminisme, algorithme de déterminisation
  5. Automate minimal, algorithme de minimisation
  6. Introduction à l'analyse lexicale par l'utilisation d'automates finis
Prérequis :
Aucun
Document(s) :
Polycopié
Mot(s) clé(s) :
Automates finis, langages réguliers, expressions régulières, déterminisme, déterminisation, minimisation
Cours en ligne :
http://www.enseirb.fr/~herbrete/IF114