Automates

Plan du cours

• Mots
  • Opérations
  • Concaténations
  • Opérations rationnelles
  • Abus de notations
  • Expressions rationelles
  • Exemples
• Automates
  • Définition
  • Lien avec les machines de Turing (Machines de Turing à une seule bande qui ne revient pas en arrière)
• Théorème de Kleene
  • Automate → expression
    • Mc-Naughton-Yamada
    • Élimination de Gauss (Lemme d'Arden)
    • Par élimination d'état
  • Expression → automate
    • Automates de Glushkov
    • Automates à ε-transitions
    • Supression des ε-transitions
• Automates déterministes
  • Définition
  • Déterminisation
    • Algorithme
    • Nombre d'états
  • Complétion et passage au complémentaire
  • Clôture par union, intersection et complémentaire
    • Intersection par passage au complémentaire
    • Intersection par produit d'automates
• Lemme de l'étoile
  • Énoncé
  • Application à la non-rationalité de certains langages
    • K = { aⁿbⁿ : n ⩾ 0 }
    • L = { w : |w|_a = |w|_b }
  • Limite du lemme : K' = K ∪ A^*baA^*
• Applications
  • Recherche de motif
  • Linguistique
  • Arithmétique des ordinateurs
  • Transductions (transformations)

Développements et compléments

• Automate minimal : existence et unicité
• Automate minimal : algorithme d'Hopcroft
• Automates bi-directionnels
• Algorithme de Brzozowski pour la minimisation
• 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.