Fiche de révision : Langages formels et automates

📋 Plan du Cours

1. Mots et opérations sur les langages
2. Grammaires régulières
3. Automates finis déterministes et non déterministes
4. Expressions régulières et équations
5. Équivalences et théorèmes fondamentaux
6. Conversions et déterminisation
7. Lemme de pompage et preuves
8. Méthodes de résolution des exercices
9. Pièges et compétences d’examen

📖 1. Mots et opérations sur les langages

🔑 Notions clés & Définitions

• Mot : Une suite finie d’éléments de V_t, de longueur |u| ; le mot de longueur nulle est le mot vide ε.
• Langage : Un sous-ensemble de V_t⋆, l’ensemble de tous les mots construits sur V_t.

📝 Points essentiels

📐 Formule — La puissance d’un mot est définie par $u^0=ε$ et $u^{p+1}=u\cdot u^p$.

📐 Formule — Le produit de langages est $L_1\circ L_2=\{u\cdot v\mid u\in L_1,\ v\in L_2\}$.

📖 2. Grammaires régulières

🔑 Notions clés & Définitions

• Grammaire régulière : Une grammaire dont chaque règle produit soit un mot terminal, soit un mot terminal suivi d’au plus un non-terminal.
• Grammaire régulière réduite : Une grammaire régulière qui possède uniquement des règles de la forme N→αM ou N→ε, avec un seul terminal α suivi d’au plus un non-terminal M.

★ À maîtriser

• La dérivation d’un mot dans une grammaire applique successivement des règles jusqu’à obtenir un mot terminal, et le langage engendré regroupe tous les mots terminaux dérivables depuis l’axiome.

Compléments

📌 Les trois contraintes de réduction d’une grammaire régulière modifient la forme des règles sans modifier le langage engendré.

💡 Astuce mémo

Règles → dérivations → langage engendré

📖 3. Automates finis déterministes et non déterministes

🔑 Notions clés & Définitions

• AFD : Un tuple (V_t,Q,q_0,F,T) où Q est fini, q_0 est initial, F est l’ensemble des états finals et T:Q×V_t→Q est une fonction de transition.
• AFN : Une transition T:Q×V_t→𝒫(Q), de sorte qu’une lettre peut mener à plusieurs états ou à aucun état.
• Mot reconnu : Un mot est reconnu par un automate s’il existe une exécution depuis l’état initial qui se termine dans un état final.

📝 Points essentiels

📌 Un AFN n’est pas plus expressif qu’un AFD, car tout AFN peut être déterminisé sans changer le langage reconnu.

💡 Astuce mémo

AFD : une destination ; AFN : plusieurs destinations possibles

📖 4. Expressions régulières et équations

🔑 Notions clés & Définitions

• Expression régulière : Construite à partir de ∅, ε et des lettres de V_t au moyen de l’union +, de la concaténation, de l’étoile ⋆ et du plus +.

★ À maîtriser

📐 Formule — La sémantique de l’itération est $L^⋆=\bigcup_{p\ge 0}L^p$ et $L^+=\bigcup_{p\ge 1}L^p$.

📐 Formule — Le lemme d’équation linéaire utilise $X=eX+f\Rightarrow X=e^⋆\cdot f$ pour obtenir une solution minimale.

Compléments

📌 Dans une expression régulière, les priorités sont ⋆ > concaténation > +, avec associativité à gauche pour la concaténation et pour +.

💡 Astuce mémo

Transitions → équations → expression régulière

📖 5. Équivalences et théorèmes fondamentaux

★ À maîtriser

📌 Les langages réguliers, reconnaissables et rationnels coïncident : un langage est régulier par grammaire si et seulement s’il est reconnaissable par automate, et si et seulement s’il est rationnel par expression régulière.

• La déterminisation construit un automate dont les états sont des parties de Q et qui reconnaît exactement le même langage que l’AFN initial.

📐 Formule — Dans la construction des parties, $F_{det}=\{K\in\mathcal P(Q)\mid K\cap F\ne\varnothing\}$ et $T_{det}(K,α)=\bigcup_{q\in K}T(q,α)$.

Compléments

• Un automate permet d’obtenir un système d’équations en associant une variable à chaque état et un terme ε aux états finals.

💡 Astuce mémo

G-A-E : grammaire, automate, expression

📖 6. Conversions et déterminisation

📝 Points essentiels

• Pour passer d’un automate à une grammaire réduite, on prend les états comme non-terminaux, l’état initial comme source, les transitions comme règles αM et les états finals comme règles ε.

• Pour passer d’une grammaire réduite à un automate, les non-terminaux deviennent des états, les règles M→αN deviennent des transitions et les règles M→ε définissent les états finals.

• Pour déterminiser un AFN, on part de {q_0}, on calcule les parties atteignables par union des transitions et on rend acceptante toute partie qui rencontre F.

💡 Astuce mémo

Grammaire → automate → parties atteignables

📖 7. Lemme de pompage et preuves

★ À maîtriser

• Le lemme de pompage affirme que si L est reconnaissable, alors il existe k>0 tel que tout mot x∈L de longueur |x|>k se décompose en x=uvw avec v≠ε, |v|<k et, pour tout n∈ℕ, uv^nw∈L.

• Pour prouver qu’un langage n’est pas reconnaissable, on suppose sa reconnaissabilité, on choisit un mot assez long, on applique le découpage du lemme, puis on choisit un n qui produit un mot hors du langage.

Compléments

• Les exemples cités de langages non reconnaissables sont:
  • {α^nβ^n∣n≥0}
  • les mots ww
  • les mots contenant autant de α que de β

💡 Astuce mémo

Plus de positions que d’états → répétition d’un état → facteur pompable

📖 8. Méthodes de résolution des exercices

★ À maîtriser

• Pour réduire une grammaire régulière, on introduit d’abord des non-terminaux intermédiaires, puis on élimine les règles N→M, et enfin on remplace N→α par N→αE avec E→ε.

• Pour résoudre un système d’équations, on isole une variable récursive avec X=e⋆·f, on la substitue dans les autres équations et on répète jusqu’à obtenir l’expression régulière recherchée.

Compléments

• Pour décider si un mot appartient à un langage, on déroule une exécution explicite de l’automate ou une dérivation explicite de la grammaire.

💡 Astuce mémo

Réduire, convertir, déterminer, pomper, résoudre

📖 9. Pièges et compétences d’examen

★ À maîtriser

📌 Le lemme de pompage est une condition nécessaire de reconnaissabilité et ne prouve jamais qu’un langage est reconnaissable.

📌 Dans un AFD, T est une fonction vers Q, tandis que dans un AFN, T est une application vers 𝒫(Q).

Compléments

📌 Dans le système d’équations associé à un automate, il faut conserver le terme f_i, notamment le terme +ε correspondant aux états finals.

• Une preuve par récurrence sur une propriété de mots engendrés par une grammaire se mène sur la longueur de la dérivation.

📊 Tableaux de synthèse

Correspondance des trois descriptions