| Automate fini déterministe. État accessible, co-accessible. Automate émondé. Langage reconnu par un automate. |
On insiste sur la richesse de systèmes dont le fonctionnement peut être modélisé par un automate. |
| Transition spontanée (ou 𝜀-transition). Automate fini non déterministe. |
|
| Déterminisation d’un automate non déterministe. |
On fait le lien entre l’élimination des transitions spontanées et l’accessibilité dans un graphe. On aborde l’élimination des transitions spontanées et plus généralement les constructions d’automates à la Thompson sur des exemples, sans chercher à formaliser complètement les algorithmes sous-jacents. |
| Construction de l’automate de Glushkov associé à une expression régulière par l’algorithme de Berry-Sethi. |
Les notions de langage local et d’expression régulière linéaire sont introduites dans cette seule perspective. |
| Passage d’un automate à une expression régulière. Élimination des états. Théorème de Kleene. |
On se limite à la description du procédé d’élimination et à sa mise en œuvre sur des exemples d’automates de petite taille; cela constitue la preuve du sens réciproque du théorème de Kleene. |
| Stabilité de la classe des langages reconnaissables par union finie, intersection finie, complémentaire. |
|
| Lemme de l’étoile. |
Soit 𝐿 le langage reconnu par un automate à 𝑛 états : pour tout 𝑢 ∈ 𝐿 tel que \|𝑢\| ≥ 𝑛, il existe 𝑥, 𝑦, 𝑧 tels que 𝑢 = 𝑥𝑦𝑧, \|𝑥𝑦\| ≤ 𝑛, 𝑦 ≠ 𝜀 et 𝑥𝑦 ∗ 𝑧 ⊆ 𝐿. |