Théorie des langages rationnels

Le séminaire de théorie des langages rationnels (THLR) de deuxième année, à l'EPITA Toulouse, en 2019-2020. Ce cours s'inspire du matériel d'origine du séminaire, mais je l'ai entièrement reconstruit : nouvelle organisation, texte rédigé de bout en bout, exemples et exercices.

Sept chapitres et sept feuilles d'exercices. Les chapitres 1 et 2 posent le vocabulaire et les expressions rationnelles ; le chapitre 3 définit les automates ; les chapitres 4 et 5 montrent qu'expressions et automates décrivent les mêmes langages (théorème de Kleene), en donnant les algorithmes pour passer des unes aux autres. Les chapitres 6 et 7 explorent les propriétés de ces langages, et leurs limites.

Les automates sont dessinés avec des conventions constantes : une flèche entrante pour un état initial, un double cercle pour un état final.

Supports de cours

1. Mots et langages : Le vocabulaire de base de tout le cours. Alphabet, mot, concaténation, préfixes et facteurs, langage, et les opérations sur les langages jusqu'à l'étoile de Kleene.
2. Expressions rationnelles : Décrire finiment des langages infinis. Les langages rationnels, les expressions qui les dénotent, leurs règles de calcul, et ce qui les sépare des regex des langages de programmation.
3. Automates finis : Une machine à mémoire finie qui lit un mot lettre à lettre et répond oui ou non. Définitions des automates déterministes, non déterministes et à transitions spontanées, et le vocabulaire pour en parler.
4. Des expressions aux automates : Compiler une expression rationnelle en automate déterministe, en trois étapes mécaniques. La construction de Thompson, l'élimination des transitions spontanées, la déterminisation par sous-ensembles.
5. Des automates aux expressions, le théorème de Kleene : Retrouver une expression rationnelle à partir d'un automate, par élimination d'états ou par résolution d'équations. On en déduit que les langages rationnels sont exactement les langages reconnaissables.
6. Propriétés de clôture : Quelles opérations préservent les langages rationnels ? Transposé, préfixes, facteurs, sous-mots, complémentaire, intersection, et le produit synchronisé, qui permet de tester l'inclusion et l'équivalence.
7. Minimisation et limites : Ce qu'un automate doit retenir, et ce qu'il ne peut pas retenir. Les résiduels, l'automate minimal et l'algorithme de Moore ; le lemme de l'étoile, pour montrer qu'un langage n'est pas rationnel.

Feuilles d'exercices

1. Mots et langages : Préfixes, facteurs et sous-mots, produits et étoiles de langages, et quelques identités à démontrer ou à réfuter. Chapitre 1.
2. Expressions rationnelles : Lire, écrire et comparer des expressions rationnelles ; passer d'une spécification en français à une expression précise. Chapitre 2.
3. Automates finis : Lire, construire, émonder, compléter et exécuter des automates, déterministes ou non. Chapitre 3.
4. Des expressions aux automates : Construction de Thompson, élimination des transitions spontanées, déterminisation, et le prix de la déterminisation. Chapitre 4.
5. Des automates aux expressions : Élimination d'états dans différents ordres, résolution d'équations par le lemme d'Arden, et une expression pour les multiples de 3 en binaire. Chapitre 5.
6. Propriétés de clôture : Transposé, complémentaire, produit synchronisé et test d'inclusion, puis quelques preuves de clôture par construction d'automates. Chapitre 6.
7. Minimisation et limites : Minimiser un DFA par l'algorithme de Moore, calculer des résiduels, et démontrer qu'un langage n'est pas rationnel. Chapitre 7.