Automates finis et applications

Les automates finis modélisent des programmes à mémoire finie : ils permettent de résoudre un problème sans dépendre d'un langage de programmation, en raisonnant sur les invariants à maintenir. Le cours part des langages et des automates finis déterministes, établit avec le théorème de Kleene l'équivalence entre automates, langages réguliers et expressions régulières, puis montre par le lemme de l'étoile que certains langages ne sont pas réguliers. Viennent ensuite les grammaires, la déterminisation des automates non déterministes et le calcul de l'automate minimal. Les TD suivent les mêmes chapitres et se terminent par une introduction à l'analyse lexicale.

Notes de cours

Cours6 pages

• Automates finis et langagesFormalisation des problèmes de décision par des langages, puis des algorithmes par des automates finis : alphabet, mot, langage, automate déterministe et complet, langage accepté.
• Expressions régulières et théorème de KleeneLangages réguliers, expressions régulières et théorème de Kleene : équivalence entre automates finis, langages réguliers et expressions régulières.
• Langages non réguliersExistence de langages non réguliers par un argument de dénombrabilité, puis lemme de l'étoile (pumping lemma) pour prouver qu'un langage n'est pas régulier.
• GrammairesGrammaires formelles : dérivation, langage généré, grammaires régulières, hiérarchie de Chomsky, arbres de dérivation et ambiguïté.
• Non-déterminisme et déterminisationÉlimination du non-déterminisme dans les automates finis : exécutions d'un AFN, clôture instantanée (epsilon-clôture) et construction par sous-ensembles.
• Automate minimal et minimisationReprésentation canonique des langages réguliers par l'automate minimal (congruence de Nerode) et algorithme de minimisation : suppression des états inaccessibles puis fusion des états équivalents.

Travaux dirigés6 pages

• TD 1 : automates finis et langagesConstruction d'automates déterministes et non déterministes, algorithme d'acceptation d'un mot, jeu des portes bascules.
• TD 2 : expressions régulièresSyntaxe et langage des expressions régulières, construction de Kleene, utilisation de grep.
• TD 3 : langages non réguliersPreuves de non-régularité par le lemme de l'étoile et propriétés de clôture des langages réguliers.
• TD 4 : grammairesLemme d'Arden, grammaires linéaires gauches et droites, arbres de dérivation, ambiguïté et construction de grammaires.
• TD 5 : non-déterminisme et déterminisationSimulation d'un AFN, construction par sous-ensembles, langage vide, universalité, inclusion et coût exponentiel de la déterminisation.
• TD 6 : automate minimalCalcul de l'automate minimal par suppression des états inaccessibles et fusion des états équivalents.

Ressources

Support de l'enseignant (Moodle)1 document

• Polycopié du cours

Sujets de TD7 documents

• Automates finis et langages
• Expressions régulières et théorème de Kleene
• Langages non réguliers
• Grammaires
• Non-déterminisme et déterminisation
• Automate minimal et minimisation
• Introduction à l'analyse lexicale