Cette unité d'enseignement propose l'étude des automates et des langages qu'ils représentent, tant du point de vue de la modélisation que des algorithmes associés utiles pour traiter automatiquement ces objets.
-
Modélisation par automates finis (déterministes ou non déterministes) et par expressions régulières
-
Algorithmes de recherche de motifs
-
Déterminisation des automates finis - Clôtures booléennes (union, intersection, complémentaire) - Test du vide et équivalence/inclusion de langages
-
Clôtures rationnelles (concaténation, étoile de Kleene) - Théorème de Kleene
-
Minimisation
-
Résiduels et lemme de l'étoile
-
Reconnaissance par monoides
-
Grammaire algébrique (modélisation des expressions arithmétiques) : algorithme de Cocke-Younger-Kasami
-
Automates à pile
-
Evocation de la hiérarchie de Chomsky