Automates et analyse lexicale

Ce cours est une introduction à la théorie des automates finis et des langages formels, ainsi qu'à l'analyse lexicale.

Les langages rationnels sont étudiés tant sous l'angle algorithmique qu'algébrique. Sont abordés en particulier des algorithmes pour transformer une expression rationnelle en automates et vice-versa, pour déterminiser un automate et le minimiser ; mais aussi le lemme d'itération ou la caractérisation de Myhill-Nerode des langages rationnels selon leur nombre de résiduels.

Enfin, l'introduction à l'analyse lexicale est une application des techniques enseignées dans ce cours à la construction des compilateurs.

Programmation en Java, les bases de la programmation orientée objet inclus, par exemple comme enseigné dans le cours Initiation à la programmation 2. 

Sujets centraux

1. Langages et opérations sur les langages
2. Expressions rationnelles
3. Automates déterministes
4. Automates non-déterministes, et déterminisation
5. Automates avec transitions “epsilon”, et élimination des transitions “epsilon”
6. Algorithme de Thompson pour la transformation d'une expression rationnelle en automate
7. Algorithme de Glushkov pour la transformation d'une expression rationnelle en automate
8. Automates généralises, et algorithme de Brzozowksi-McCluskey pour la transformation d'un automate en expression rationnelle
9. Équivalence entre expression rationnelles et automates, propriétés de clôture de la classe des langages reconnaissables
10. Analyse lexicale : principe, et utilisation d'un générateur du type lex
11. Le lemme d'itération, et son utilisation pour montrer qu'un langage n'est pas reconnaissable
12. Calcul du résiduel d'une expression rationnelle par rapport à une lettre, et construction de l'automate des résiduels pour une expression rationnelle
13. Le théorème de Myhill-Nerode, et utilisation des résiduels pour montrer qu'un langage n'est pas reconnaissable
14. Minimisation d'automates déterministes par la méthode de Moore

Sujets potentiellement traités

1. Le lemme d'Arden, et son utilisation pour transformer un automate en expression rationnelle
2. Aspects avancés de lex : utilisation d'états multiples, utilisation d'une table de hachage
3. Minimisation d'automates déterministes par la méthode de Brzozoswki
4. Automates bi-directionnels