Cours/TD Automates Avancés et Applications
M1 Informatique 2022-2023

• Cours : Vendredi 10h45-12h45. Salle 2027 (Sophie Germain)
• TD : Mardi 14h00-16h00. Salle 2027 (Sophie Germain)

Enseignants :

• Daniela Petrisan
• Arnaud Sangnier

• Semaine 1 : Expressions rationnelles, automates finis, traduction d'une expression rationnelle en un automate par la méthode des automates normalisés
• Semaine 2 : Traduction d'un automate fini en une expression rationnelle par la méthode par éliminiation, automates déterministes, lemme de l'étoile
• Semaine 3 : Lemme de l'étoile fort. Grammaire algébriques.
• Semaine 4 : Lemme de l'étoile fort. Grammaire algébriques propres.
• Semaine 5 :Automates à piles. De l'automate à la grammaire et vice-versa.
• Semaine 6 :Révisions.

• TD 1 et sa correction.
• TD 2.
• TD 3.
• TD 4.
• TD 5.

• Résultat.
• Enoncé -> à refaire et à rendre le jour de l'examen

• Partiel 2021/2022.

• O. Carton, Langages formels, calculabilité et complexité.
• D. Perrin, J.-E. Pin, Infinite words.