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.
L'objectif de l'UE est d'étudier différentes classes de langages, depuis les langages réguliers jusqu'aux langages algébriques, afin d'étudier le compromis entre expressivité et décidabilité. Par ailleurs, cette étude sera située dans le cadre de la hiérarchie de Chomsky.
Contenu :
Sur les langages réguliers :
- Automates finis, expressions régulières
- Théorème de Kleene : algorithme de Glushkov et approche par les équations (Lemme d'Arden)
- Propriétés de clôture : opérations rationnelles, opérations booléennes
- Résiduels, automates des résiduels
- Déterminisation des automates finis
- Algorithmique : test du vide, inclusion, équivalence
- Lemme de l'étoile
Sur les langages algébriques :
- Grammaires algébriques, dérivation, arbre de dérivation
- Application à la modélisation des expressions arithmétiques
- Automates à pile
- Equivalence entre grammaires algébriques et automates à pile
- Automates à pile déterministes : définition, propriétés
- Algorithme Cocke-Younger-Kasami
