Automates avancés en
M1 en 2014/2015
- Présentation du cours
- Cours n° 1 : rappels
- alphabet, mots, concaténation, langages
- langages rationnels
- automates, chemins, chemins acceptants
- Cours n° 2 : théorème de Kleene
- automates émondés
- automates normalisés et construction inductive
- automates de Glushkov
- algorithme de McNaughton et Yamada
- algorithme par élimination
- résolution de système avec le lemme d'Arden
- Cours n° 3 : automates déterministes
- déterminisation d'un automate
- minimisation d'un automate déterministe
- Algorithme de Moore
- Algorithme d'Hopcroft
- Cours n° 4 : lemmes d'itération
- lemme d'itération (version faible)
- application au langage { anbn : n ⩾ 0 }
- automate pour le complémentaire
- automates pour l'intersection (par le complémentaire ou direct)
- application au langage { w : |w|a = |w|b }
- exemple de langage non rationnel qui vérifie le lemme
- lemme d'itération (version forte)
- Cours n° 5 : grammaires
- définition
- exemples
- S → aS + b et L = a*b
- S → aSb + ε et L = { anbn : n ⩾ 0 }
- S → aSa + bSb + a + b + ε et l'ensemble des palindromes
- S → aSbS + bSaS + ε et
L = { w : |w|a = |w|b }
- grammaires réduites
- Cours n° 6 : grammaires (suites)
- grammaires linéaires droites (gauches)
- grammaires propres
- forme normale de Greibach
- Cours n° 7 : automates à pile
- définition
- automate à pile acceptant les palindromes
- définition du calcul d'un automate à pile
- automate à pile acceptant l'ensemble
L = { w : |w|a = |w|b }
- équivalence entre grammaires et automates à pile
- Cours n° 8 : lemmes d'itération
- lemme d'Ogden
- application
- Cours n° 9 : mots infinis
- introduction et définitions
- mot infini, Aω
- mot périodique et mot ultimement pédiodique
- développement dans une base des nombres réels
- expressions rationnelles
- produit (concaténation) ux d'un mot fini u
et un mot infini x
- produit LX = { ux : u ∈ L et x ∈ X }
- produit u0u1u2⋯ d'une suite de
mots finis (un)n⩾0.
- Lω = { u0u1u2⋯ :
un ∈ L }
- exemples de langages
(ab)ω, aa(ab)ω, (a*b)ω,
A*bω, A*(aω + bω),
(ab+b)ω, A*(ab+b)ω
- Cours n° 10 : automates de Büchi
- définition et exemples
- équivalence entre expressions rationnelles et automates
- Cours n° 11 : automates de Büchi déterministes
- définition et exemples
- langages limites et automates déterministes
- Cours n° 12 : automates de Muller
- définition et exemples
- construction de Safra
- Examen : lundi 1er juin de 8h30 à 11h30 en amphi 13E. Les
seuls documents autorisés sont 2 feuilles de memento.
- Rattrapage : mardi 30 juin de 12h à 15h en amphi 3B. Les
seuls documents autorisés sont 2 feuilles de memento.