Fiche de révision : Théorie des langages rationnels

📋 Plan du Cours

1. Alphabet, mots et langages
2. Opérations sur les mots
3. Distances entre les mots
4. Décidabilité des langages
5. Opérations sur les langages
6. Expressions régulières
7. Sémantique des expressions régulières
8. Langages rationnels et propriétés
9. Automates finis et reconnaissance
10. Déterminisme et transitions spontanées
11. Construction et simplification des automates
12. Suppression des transitions epsilon
13. Élagage des automates
14. Déterminisation par ensembles d’états
15. Lemme de pompage et non-rationalité
16. Non-rationalité et mémoire des automates
17. Minimisation des automates déterministes
18. Algorithme de Moore

📖 1. Alphabet, mots et langages

🔑 Notions clés & Définitions

• Langage : Ensemble de suites d’objets élémentaires auxquelles on attribue une signification.
• Alphabet : Ensemble fini Σ de symboles dont les éléments sont appelés des lettres.
• Mot : Suite finie, éventuellement vide, de lettres de Σ, et le mot vide est noté ε.
• Langage : Ensemble de mots tel que L ⊆ Σ∗, qui peut être fini ou infini.

★ À maîtriser

📌 Σ∗ est l’ensemble de tous les mots sur Σ, tandis que Σ+ = Σ∗ \ {ε} est l’ensemble des mots non vides sur Σ.

Compléments

• Sur Σ = {0, 1}, l’ensemble des mots contenant un nombre pair de 1 est un langage infini.

💡 Astuce mémo

Alphabet → mot → langage

📖 2. Opérations sur les mots

🔑 Notions clés & Définitions

• Longueur : Nombre total de lettres, avec |ε| = 0.
• Concaténation : La concaténation de w1 = a1…an et w2 = b1…bm est le mot w1 · w2 = a1…anb1…bm obtenu en plaçant w2 après w1.
• Préfixe, suffixe et facteur : Pour des mots w, x, y et z, x est un préfixe de w si w = x · y, z est un suffixe si w = y · z, et y est un facteur si w = x · y · z.
• Palindrome : Le miroir d’un mot w = w1…wn est wR = wn…w1, et w est un palindrome lorsqu’il vérifie w = wR.

★ À maîtriser

📌 La concaténation vérifie $|w_1 \cdot w_2| = |w_1| + |w_2|$ et ε · w1 = w1 · ε = w1, donc ε est son élément neutre.

📌 La concaténation est associative, car w1 · (w2 · w3) = (w1 · w2) · w3, mais elle n’est pas commutative, car w1 · w2 peut différer de w2 · w1.

Compléments

• Pour w = 011101, on a |w| = 6 et |w|1 = 4.

💡 Astuce mémo

Préfixe au début, suffixe à la fin, facteur n’importe où

📖 3. Distances entre les mots

🔑 Notions clés & Définitions

• Distance : Une distance sur un ensemble E est une fonction d : E² → R+ vérifiant la séparation, la symétrie et l’inégalité triangulaire.
• Distance d’édition : La distance d’édition de(w1,w2) entre deux mots de Σ∗ est le nombre minimal d’insertions et de suppressions d’une lettre nécessaires pour transformer w1 en w2.

★ À maîtriser

📐 Formule — La séparation vérifie $d(x,y)=0 \Longleftrightarrow x=y$, la symétrie vérifie $d(x,y)=d(y,x)$ et l’inégalité triangulaire vérifie $d(x,y)+d(y,z)\ge d(x,z)$.

Compléments

• La distance d’édition de(dog, bugs) vaut 5, par exemple avec deux suppressions et trois insertions.

💡 Astuce mémo

Insertion ou suppression → transformation minimale → distance

📖 4. Décidabilité des langages

🔑 Notions clés & Définitions

• Langage décidable : Langage pour lequel il existe un algorithme A qui répond vrai pour tout w ∈ L et faux pour tout w ∉ L.

★ À maîtriser

• Le langage des programmes qui s’arrêtent sur une entrée donnée est indécidable, quel que soit le langage de programmation.

Compléments

• Le langage des nombres premiers est décidable, notamment par un algorithme comme le crible d’Ératosthène.

• Le langage vide et le langage Σ∗ sont décidables respectivement par les algorithmes qui répondent toujours faux et toujours vrai.

• Le langage des programmes qui s’arrêtent en moins de dix secondes sur une entrée donnée est décidable en compilant puis en exécutant le programme avec une limite de dix secondes.

💡 Astuce mémo

Arrêt en temps borné décidable, arrêt sans borne indécidable

📖 5. Opérations sur les langages

🔑 Notions clés & Définitions

• Union de langages : Pour deux langages A et B, w appartient à A ∪ B si et seulement si w appartient à A ou à B.
• Complément : Le complémentaire A∁ d’un langage A contient les mots de Σ∗ qui n’appartiennent pas à A, et A∁ = Σ∗ \ A.
• Concaténation de langages : La concaténation de deux langages L1 et L2 est L1 · L2 = {w1 · w2 | w1 ∈ L1 et w2 ∈ L2}.
• Étoile de Kleene : L’étoile de Kleene est L∗ = ⋃n≥0 Ln, l’ensemble des mots obtenus en concaténant un nombre fini, éventuellement nul, de mots de L, tandis que L+ = ⋃n≥1 Ln impose au moins un mot.
• Préfixe d’un langage : Pref(L) est l’ensemble des mots qui sont des préfixes d’au moins un mot de L, et non nécessairement de tous les mots de L.

📝 Points essentiels

📌 Les opérations sur les langages vérifient A∁∁ = A, A ∪ A∁ = Σ∗, (A ∪ B)∁ = A∁ ∩ B∁ et (A ∩ B)∁ = A∁ ∪ B∁.

📌 Pour k ∈ N, L0 = {ε} et Lk est l’ensemble des mots obtenus en concaténant k mots de L, qui peuvent être différents, donc Lk ≠ {uk | u ∈ L}.

💡 Astuce mémo

Concaténation répétée → puissances → étoile de Kleene

📖 6. Expressions régulières

🔑 Notions clés & Définitions

• Expression régulière : Une expression régulière est un motif formel qui décrit un langage au moyen de l’alternation, de la concaténation et de l’étoile de Kleene.

📝 Points essentiels

📌 Dans une expression régulière, e? = e + ε représente l’optionnel, e+ = ee∗ au moins une occurrence, et en représente exactement n occurrences de e.

📌 La syntaxe inductive de RegΣ contient les atomes ∅, ε et chaque lettre a ∈ Σ, puis les expressions e1 + e2, e1e2 et e1∗ lorsque e1 et e2 sont déjà des expressions régulières.

• La sémantique associe à chaque expression régulière e un langage L(e) en interprétant ses atomes et ses trois opérateurs.

💡 Astuce mémo

Atomes → alternation, concaténation ou étoile → langage rationnel

📖 7. Sémantique des expressions régulières

🔑 Notions clés & Définitions

• Sémantique d’une expression régulière : Langage L(e) défini inductivement à partir de la structure de e.

📝 Points essentiels

📐 Formule — Les cas de base vérifient $L(∅)=∅$, $L(ε)=\{ε\}$ et, pour toute lettre a ∈ Σ, $L(a)=\{a\}$.

📐 Formule — La concaténation, l’union et l’étoile vérifient respectivement $L(e_1e_2)=L(e_1)\cdot L(e_2)$, $L(e_1+e_2)=L(e_1)\cup L(e_2)$ et $L(e_1^*)=L(e_1)^*$.

💡 Astuce mémo

Bases ∅, ε, lettres, puis concaténation, union et étoile

📖 8. Langages rationnels et propriétés

🔑 Notions clés & Définitions

• Langage rationnel : Langage L ⊆ Σ* tel qu’il existe une expression régulière e ∈ RegΣ vérifiant L=L(e), c’est-à-dire s’il appartient à RatΣ.

★ À maîtriser

📌 L’union, la concaténation et l’étoile de langages rationnels sont rationnelles, tandis que cette définition syntaxique ne permet pas d’affirmer directement la clôture par intersection et complément.

📌 Tout langage rationnel est décidable ; par conséquent, un langage indécidable tel que H n’est pas rationnel.

Compléments

• Tout langage fini {w₁,…,wₙ} est rationnel, car il est décrit par l’expression régulière w₁+…+wₙ.

• Le langage vide ∅ et le langage Σ* de tous les mots sont rationnels ; si Σ={a₁,…,aₙ}, alors Σ* est décrit par (a₁+…+aₙ)*.

💡 Astuce mémo

Rationnel = décrit par une expression ; indécidable ≠ rationnel

📖 9. Automates finis et reconnaissance

🔑 Notions clés & Définitions

• Automate fini : Quintuplet A=(Q,Σ,δ,I,F), où Q est un ensemble fini d’états, Σ un alphabet fini, δ⊆Q×Σ×Q un ensemble d’arêtes, I un ensemble non vide d’états initiaux et F un ensemble d’états acceptants.
• Chemin étiqueté : Suite d’arêtes consécutives portant successivement les lettres w₁,…,wₙ et partant d’un état initial.
• Acceptation d’un mot : Existence d’un chemin étiqueté par w allant d’un état initial à un état acceptant.
• Langage d’un automate : Ensemble des mots acceptés par l’automate A.

📝 Points essentiels

📌 Un mot peut être refusé parce qu’un chemin existe sans aboutir à un état acceptant, ou parce qu’aucun chemin ne porte ce mot.

💡 Astuce mémo

Chemin initial étiqueté par le mot → état final → acceptation

📖 10. Déterminisme et transitions spontanées

🔑 Notions clés & Définitions

• Automate déterministe : Possède exactement un état initial et, pour chaque état q et chaque lettre a∈Σ, au plus une arête sortante de q étiquetée par a.
• Automate non déterministe : Automate qui ne respecte pas les conditions du déterminisme.
• Automate complet : Pour chaque lettre a∈Σ et chaque état q, existence d’au moins une arête sortante de q étiquetée par a.
• Transition spontanée : Transition étiquetée par ε qui peut être empruntée sans lire de lettre de l’entrée.

★ À maîtriser

📌 Dans un NFA, un mot est accepté dès qu’il possède au moins un chemin acceptant, même si d’autres chemins étiquetés par le même mot sont rejetants.

Compléments

📌 Si un automate est déterministe, alors chaque mot w∈Σ* possède au plus un chemin étiqueté par w.

📌 Un automate complet possède au moins un chemin étiqueté pour chaque mot de Σ*, tandis qu’un automate déterministe possède au plus un tel chemin.

💡 Astuce mémo

DFA : au plus un chemin ; NFA : un seul chemin acceptant suffit

📖 11. Construction et simplification des automates

🔑 Notions clés & Définitions

• Fermeture ε avant : Ensemble ε-forwardA(q)={p∈Q | q ε→*A p} des états atteignables depuis q en utilisant uniquement des transitions ε, y compris q lui-même.

★ À maîtriser

• 🔄 La complétion d’un automate suit ces étapes:
  1. Ajouter un état puits non acceptant
  2. Ajouter à l’état puits une boucle pour chaque lettre
  3. Rediriger vers l’état puits toutes les arêtes manquantes

📌 Le théorème de Kleene affirme que pour toute expression régulière e∈RegΣ, il existe un ε-NFA A sur Σ tel que L(e)=L(A).

• L’algorithme de Thompson construit inductivement un ε-NFA ayant un unique état initial i et un unique état acceptant distinct f, en traitant les cas de base, la concaténation, l’union et l’étoile de Kleene.

📌 Pour toute expression e, si n est le nombre d’occurrences de ε, ∅, +, *, et des lettres de Σ dans e, hors parenthèses, l’automate de Thompson possède exactement 2n états.

• La suppression arrière des transitions ε consiste à calculer les chemins ε, à ajouter pour chaque motif q₀ ε→*A q₁ a→q₂ une arête q₀ a→q₂, puis à supprimer toutes les transitions ε.

Compléments

• Un algorithme itératif de point fixe part d’un ensemble de cas de base, applique des règles pour construire une suite croissante d’ensembles, puis s’arrête lorsqu’un ensemble Sn vérifie Sn=Sn+1.

💡 Astuce mémo

Thompson construit ; la fermeture ε puis la suppression simplifient

📖 12. Suppression des transitions epsilon

🔑 Notions clés & Définitions

• Fermeture epsilon avant : Ensemble des états atteignables depuis q en suivant uniquement des transitions ε.

★ À maîtriser

• Le calcul itératif de la fermeture epsilon initialise chaque cellule avec l’état q et ses successeurs immédiats par ε, ajoute ensuite les fermetures déjà calculées des états présents, puis s’arrête lorsque deux colonnes successives sont identiques.

📌 Pour chaque état q et chaque état p appartenant à ε_A^forward(q), toute transition p x→_A r étiquetée par une lettre x de l’alphabet donne une transition q x→ r dans l’automate sans transitions ε.

📌 Si un état acceptant r appartient à ε_A^forward(p), alors p doit également être déclaré acceptant dans l’automate sans transitions ε.

Compléments

• Tout ε-NFA A sur l’alphabet Σ possède un NFA équivalent A′ sur Σ ayant le même nombre d’états.

💡 Astuce mémo

Fermeture epsilon, nouvelles transitions, états finaux

📖 13. Élagage des automates

🔑 Notions clés & Définitions

• État accessible : État qui peut être atteint depuis un état initial.
• État co-accessible : État depuis lequel un état final peut être atteint.

📝 Points essentiels

📌 Un état est utile s’il est à la fois accessible et co-accessible ; il est inutile dans le cas contraire.

• L’élagage conserve uniquement les états à la fois accessibles et co-accessibles : on recherche d’abord les accessibles depuis les états initiaux, puis les co-accessibles par une recherche depuis les états finaux en inversant les arêtes.

📌 La suppression des états inutiles produit un automate élagué équivalent à l’automate initial.

💡 Astuce mémo

Accessible depuis l’initial, co-accessible vers le final

📖 14. Déterminisation par ensembles d’états

🔑 Notions clés & Définitions

• Construction par sous-ensembles : La construction par sous-ensembles transforme un NFA en DFA en étiquetant les états du DFA par des ensembles d’états du NFA.

📝 Points essentiels

📌 L’état initial du DFA est étiqueté par I, l’ensemble des états initiaux du NFA.

📐 Formule — Pour un ensemble S et une lettre a, le successeur du DFA est l’ensemble $S_a=\{q\mid\exists p\in S,\ p\xrightarrow{a}_A q\}$ des états atteignables par a depuis au moins un état de S.

📌 Un état du DFA est acceptant si son étiquette contient au moins un état acceptant du NFA.

• La construction pratique remplit une table avec l’ensemble initial, calcule ses successeurs pour chaque lettre, ajoute chaque ensemble inédit comme nouvelle ligne, répète jusqu’à épuisement des ensembles, puis rend acceptants les ensembles contenant un état final du NFA.

• Un DFA équivalent complet à un NFA possédant n états peut avoir jusqu’à $2^n$ états, car l’ensemble des sous-ensembles d’un ensemble de n états contient $2^n$ éléments.

💡 Astuce mémo

Chaque état du DFA est une boîte contenant plusieurs états possibles du NFA

📖 15. Lemme de pompage et non-rationalité

🔑 Notions clés & Définitions

• Lemme de pompage : Pour tout langage rationnel L, il existe un seuil n₀ tel que tout mot w de L de longueur au moins n₀ se décompose en w=x·y·z avec y≠ε et tous les mots de x·y*·z appartiennent à L.

★ À maîtriser

📌 Tout langage rationnel est décidable, car il est reconnu par un DFA et l’exécution de ce DFA sur un mot termine après un nombre linéaire d’opérations en la taille du mot.

• Dans un DFA à n états acceptant un mot w de longueur strictement supérieure à n, le principe des tiroirs impose qu’un état soit visité au moins deux fois, ce qui décompose w en w=x·y·z avec y≠ε et crée une boucle répétable.

📌 Le langage L={aⁿbⁿ | n∈N} est décidable mais non rationnel.

• Pour montrer que L={aⁿbⁿ | n∈N} n’est pas rationnel, on suppose sa rationalité, on applique le lemme au mot aⁿ⁰bⁿ⁰, puis on distingue selon que le facteur pompé contient plus de a, autant de a que de b, ou plus de b, chaque cas conduisant à une contradiction.

Compléments

📐 Formule — Pour un mot de L={aⁿbⁿ | n∈N}, le nombre de a et le nombre de b sont égaux, soit $|w|_a=|w|_b$.

💡 Astuce mémo

Mot trop long → état répété → boucle pompable

📖 16. Non-rationalité et mémoire des automates

★ À maîtriser

• Pour montrer que le langage L = {a^n b^n | n ∈ N} n’est pas rationnel, le lemme de l’étoile est appliqué en distinguant les trois positions possibles du facteur pompé dans un mot de L.

• Un langage rationnel est reconnu par un algorithme utilisant une quantité constante de mémoire indépendante de la taille de l’entrée.

• L’algorithme qui décide L = {a^n b^n | n ∈ N} lit d’abord les a en incrémentant un compteur, lit ensuite les b en le décrémentant, puis accepte exactement si toute l’entrée a été parcourue et si le compteur vaut zéro.

• Pour reconnaître les entiers divisibles par 3, un automate lit les chiffres de gauche à droite et mémorise le reste modulo 3 de leur somme.

• Pour reconnaître les mots ayant un nombre pair de a et un nombre impair de b, un automate mémorise séparément les deux parités au moyen de quatre états.

Compléments

• Dans un automate fini déterministe, chaque état représente une configuration possible de la mémoire limitée de l’algorithme.

• Les expressions rationnelles ne peuvent pas reconnaître les parenthèses correctement appariées.

• La reconnaissance des entiers divisibles par 3 nécessite trois états, correspondant aux restes 0, 1 et 2 modulo 3 de la somme des chiffres.

💡 Astuce mémo

Compteur non borné → langage non rationnel

📖 17. Minimisation des automates déterministes

🔑 Notions clés & Définitions

• États indistinguables : Deux états q1 et q2 d’un automate déterministe sont indistinguables si, pour tout mot w ∈ Σ*, l’automate accepte w depuis q1 si et seulement s’il l’accepte depuis q2.

★ À maîtriser

• La minimisation consiste à regrouper les états indistinguables en classes d’équivalence puis à fusionner les états d’une même classe.

• Le théorème de Myhill-Nerode affirme que tout langage rationnel possède un unique automate déterministe minimal, dont le nombre d’états est égal au nombre de classes d’indistinguishabilité.

Compléments

• Pour prouver que deux états sont distinguables, il suffit de trouver un mot accepté depuis l’un des états mais refusé depuis l’autre.

📌 Si p1 et p2 sont indistinguables et que leurs transitions sur une lettre a mènent respectivement à q1 et q2, alors q1 et q2 sont aussi indistinguables.

💡 Astuce mémo

Indistinguables se fusionnent, distinguables restent séparés

📖 18. Algorithme de Moore

🔑 Notions clés & Définitions

• Produit synchronisé : Le produit synchronisé de deux automates fait évoluer simultanément les deux automates et représente leur configuration par une paire d’états.

★ À maîtriser

• L’algorithme de Moore initialise les classes avec les états acceptants F et les états non acceptants Q \ F, examine les successeurs pour chaque lettre, scinde les classes en conflit et répète jusqu’à stabilisation.

📌 Dans la table de Moore, il y a conflit lorsque deux états d’une même classe ont, pour une même lettre, des successeurs appartenant à des classes différentes.

• Une fois la table stabilisée, chaque classe devient un état du nouvel automate, la classe contenant l’état initial devient initiale et toute classe contenant un état acceptant devient acceptante.

• L’algorithme de Brzozowski–McCluskey transforme un automate en expression rationnelle en ajoutant si nécessaire un état initial et un état acceptant uniques, puis en supprimant progressivement les arêtes et les états jusqu’à obtenir une seule arête entre ces deux états.

📌 Lorsqu’un état q est supprimé, chaque chemin entrant dans q est combiné avec chaque chemin sortant de q, en tenant compte de la boucle éventuelle sur q.

• Tout automate fini déterministe, non déterministe ou avec transitions ε reconnaît le même langage qu’une expression rationnelle appropriée. — Brzozowski–McCluskey

• Les opérations qui préservent la rationalité sont:

  • Union
  • Concaténation
  • Étoile de Kleene
  • Complémentation
  • Intersection
  • Préfixes
  • Suffixes
  • Facteurs
  • Miroir

📌 Dans le produit synchronisé A1 × A2, l’état initial est (i1, i2), et un état (f1, f2) est acceptant si et seulement si f1 et f2 sont acceptants dans leurs automates respectifs.

• Pour décider si un langage rationnel est vide, on effectue une recherche en profondeur depuis l’état initial et on vérifie si un état acceptant est atteignable.

• Pour tester l’égalité de deux langages rationnels, on construit des DFA complets, leurs compléments et les deux produits synchronisés correspondant aux différences dans chaque sens, puis on vérifie que ces deux produits sont vides.

Compléments

• La suppression d’un état q crée |arêtes entrantes| × |arêtes sortantes| arêtes correspondant à toutes les combinaisons de chemins possibles.

📐 Formule — Si A1 possède n1 états et A2 possède n2 états, alors le produit synchronisé A1 × A2 possède au plus $n_1 \times n_2$ états.

• Si les deux langages ne sont pas égaux, la recherche peut fournir un contre-exemple w appartenant à l’un des langages mais pas à l’autre.

💡 Astuce mémo

Initialiser, comparer, scinder, itérer, construire

📊 Tableaux de synthèse

Opérations sur les mots et les langages

DFA, NFA et automate complet