MAT995N - Théorie algébrique des automates
Automates finis. Langages reconnaissables. Opérations rationnelles sur les langages. Langages rationnels (réguliers). Théorème de Kleene: équivalence entre rationalité et reconnaissabilité. Algorithmes sous-jacents au théorème de Kleene: expressions rationnelles et leurs dérivées, chemins dans un graphe orienté, étoile d’une matrice. Minimisation des automates. Monoïde syntaxique d’un langage. Théorème de Schützenberger: équivalence entre langages apériodiques et langages sans étoile. Théorème de McNaughton sur les langages définis par leurs facteurs. Théorème de Simon sur les langages définis par leurs sous-mots. Théorème sur les langages birécurrents et la semi-simplicité de l’algèbre syntaxique. Fonctions séquentielles. Offert à l'Hiver 2024.