Objectif : comprendre le formalisme de machine à état fini et les algorithmes reliés et les utiliser pour la modélisation. Comprendre et utiliser les formalismes d’expression régulières et de grammaires pour modéliser des langages. Comprendre l’utilisation de traduction d’un langage en un autre.
Guidés par la hiérarchie de Chomsky, nous étudierons principalement deux classes de langages : les langages réguliers et les langages algébriques. Pour chacune de ces classes, nous étudierons les propriétés fondamentales de la classe, les avantages des différentes présentations (automates vs expressions), comment les utiliser en modélisation, ainsi que les algorithmes associés utiles pour traiter automatiquement ces objets.
Plus précisément, nous étudierons :
- Modélisation par automates finis (déterministes et 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
- Résiduels et minimisation
- Lemme de l’étoile
- Grammaires algébriques (modélisation des expressions arithmétiques)
- Automates à pile
