Automates
Plan du cours
- Mots
- Opérations
- Concaténations
- Opérations rationnelles
- Abus de notations
- Expressions rationelles
- Exemples
- Automates
- Définitions
- Lien avec les machines de Turing
(Machines de Turing qui n'écrit pas sur son entrée)
- Théorème de Kleene
- Automates -> expression
- Mc-Naughton-Yamada
- Élimination de Gauss (Lemme d'Arden)
- Par élimination d'état
- Expression -> automates
- Automates de Glushkov
- Automates à epsilon-transitions
- Automates normalisé
- Automates déterministes
- Applications
Développements et compléments
- Automate minimal : existence et unicité
- Automate minimal : algorithme d'Hopcroft
- Construction du groupe libre
- Déterminisation : exemple pour la borne inf exacte
- Automates alternants
- Automates d'arbres
- Automates de mots infinis
- Lien avec la logique MSO
- Approche algébrique
- Machines qui n'écrit pas sur son entrée
- Machines en temps o(n log n)
- Machines en espace o(log log n)
- Transducteurs
Dans le programme
- Automates finis. Langages reconnaissables. Existence de langages
non reconnaissables. Déterminisation. Propriétés de clôture des
langages reconnaissables. Exemples d’application.
- Expressions rationnelles. Langages rationnels. Théorème de
Kleene.