Support de Cours Théorie des Langages et des Automates

Chapitre I - Alphabet et langages

Exercice 1 - Preuve par récurrence du miroir d'une concaténation

Question : Montrer par récurrence que (ωu)R = uR . ωR pour tout entier k tel que |u|=k.

Solution : Nous devons démontrer que l'opération miroir (reverse) s'applique à la concaténation de deux mots en inversant leur ordre.

• Base de la récurrence (k = 0) : Si |u| = 0, alors u = ε (la chaîne vide). (ωε)R = ωR De plus, εR . ωR = ε . ωR = ωR. L'égalité (ωε)R = εR . ωR est donc vraie pour k = 0.

• Hypothèse de récurrence : Supposons que la propriété est vraie pour un certain entier n. C'est-à-dire que pour tout mot x de taille n (|x| = n), on a : (ωx)R = xR . ωR.

• Étape de récurrence (k = n + 1) : Soit x un mot de taille n + 1. Nous pouvons décomposer x sous la forme x = u . a, où u est un mot de taille n (|u| = n) et a ∈ Σ (un seul symbole). (ωx)R = (ω(ua))R = ((ωu)a)R Par la définition de l'image (reverse) d'une chaîne se terminant par un caractère unique, on obtient : ((ωu)a)R = a . (ωu)R D'après notre hypothèse de récurrence appliquée à u (puisque |u| = n), nous savons que (ωu)R = uR . ωR. En remplaçant, on obtient : a . (ωu)R = a . (uR . ωR) = (a . uR) . ωR Or, par définition, (ua)R = a . uR. Donc : (a . uR) . ωR = (ua)R . ωR = xR . ωR. L'hypothèse est démontrée pour k = n + 1. La propriété est donc vraie pour tout k.

Exercice 2 - Fermeture de Kleene sur un langage

Question : Soit Σ = {0, 1} et L = { ω ∈ Σ* : ω contient un nombre de 0 ≠ nombre de 1 }. Montrez que L* = Σ*.

(Note : le caractère „ dans le texte d'origine est un défaut d'extraction désignant le symbole de différence ≠).

Solution : Pour montrer que L* = Σ*, nous devons prouver la double inclusion : L* ⊆ Σ* et Σ* ⊆ L*.

1. Preuve que L ⊆ Σ :** Par définition de la fermeture de Kleene, si L est un langage défini sur l'alphabet Σ (donc L ⊆ Σ*), alors toute concaténation de mots de L appartient également à Σ*. Donc, L* ⊆ Σ*.

2. Preuve que Σ ⊆ L :** Observons les mots de taille 1 dans L. Le mot "0" contient un '0' et zéro '1' (1 ≠ 0), donc "0" ∈ L. Le mot "1" contient zéro '0' et un '1' (0 ≠ 1), donc "1" ∈ L. Puisque {0} ∈ L et {1} ∈ L, l'alphabet complet Σ = {0, 1} est inclus dans L (Σ ⊆ L). Si un ensemble A est inclus dans un ensemble B, alors A* ⊆ B*. Par conséquent, Σ* ⊆ L*.

Les deux inclusions étant vérifiées, on conclut que L* = Σ*.

Chapitre II - Représentation finie des langages

Exercice 1 - Expressions régulières

Question : Donner les expressions régulières qui génèrent les langages L1 à L7 sur l'alphabet Σ = {a, b}.

(Note : le symbole ¨ dans la source d'origine représente l'opérateur d'union logique. Nous utiliserons le symbole ∪ pour plus de clarté algorithmique).

Solutions :

• L1 = {w ∈ {a,b}*, tel que w contient exactement bbb} En interprétant strictement "contient exactement la séquence et rien d'autre" : Expression : bbb

• L2 = {w ∈ {a,b}*, tel que w contient la sous chaîne bbb} Le mot peut commencer et se terminer par n'importe quelle séquence de 'a' et de 'b'. Expression : (a ∪ b)* bbb (a ∪ b)*

• L3 = {w ∈ {a,b}*, tel que w contient seulement 3b, le reste c'est des a's} Il y a exactement trois 'b', séparés et entourés par un nombre quelconque de 'a' (y compris zéro). Expression : a* b a* b a* b a*

• L4 = {w ∈ {a,b}*, tel que w contient un nombre de a divisible par 3} Des blocs contenant exactement trois 'a' et un nombre arbitraire de 'b' peuvent être répétés. Expression : (b* a b* a b* a)* b*

• L5 = {w ∈ {a,b}*, tel que w ne contient pas 3b consécutifs} Chaque occurrence de 'b' ou 'bb' doit être séparée par au moins un 'a', et le mot peut se terminer par un, deux ou zéro 'b'. Expression : (a ∪ ba ∪ bba)* (ε ∪ b ∪ bb)

• L6.a = {w ∈ {a,b}*, tel que w contient un nombre impaire de b} On isole un 'b' impair, et on l'entoure de séquences contenant un nombre pair de 'b' (ou de simples 'a'). Expression : a* b a* (b a* b a*)*

• L6.b = {w ∈ {a,b}*, tel que w contient un nombre paire de a} (Note : il y a deux L6 dans l'énoncé) Similaire à la logique de parité précédente, mais appliquée sur les 'a'. Expression : b* (a b* a b*)*

• L7 = {w ∈ {a,b}*, tel que w contient la sous chaîne aaa ou la sous chaîne bbb mais pas les deux en même temps} Il s'agit de l'union de deux langages : L(contient aaa ET ne contient pas bbb) ∪ L(contient bbb ET ne contient pas aaa). Pour générer un mot sans "bbb" mais contenant "aaa", on s'assure que les blocs de "a" sont séparés par des "b" courts (b ou bb), et on force l'insertion d'au moins un bloc "aaa". Soit E1 (contient aaa, sans bbb) = (ε ∪ b ∪ bb) ((a ∪ aa)(b ∪ bb))* aaa a* ((b ∪ bb)a+)* (ε ∪ b ∪ bb) Soit E2 (contient bbb, sans aaa) = (ε ∪ a ∪ aa) ((b ∪ bb)(a ∪ aa))* bbb b* ((a ∪ aa)b+)* (ε ∪ a ∪ aa) Expression finale : E1 ∪ E2

Chapitre III - Automates à états finis

Exercice 1 - Déterminisation d'un automate (NFA vers DFA)

Question : Construire le DFA pour le NFA défini dans la table source (états de 0 à 10, avec des ε-transitions).

Solution : Pour convertir le NFA en DFA, nous utilisons l'algorithme des sous-ensembles avec la clôture epsilon (ε-fermeture). L'alphabet est Σ = {a, b}. L'état initial du NFA est 0, et l'état final est 10.

1. Calcul de l'état initial du DFA (A) : A = ε-fermeture(0) = {0, 1, 2, 4, 7}

2. Calcul des transitions depuis A :

• Transiter(A, a) : Depuis {0, 1, 2, 4, 7}, une transition 'a' mène aux états {3, 8}. ε-fermeture({3, 8}) = {1, 2, 3, 4, 6, 7, 8}. C'est notre nouvel état B.
• Transiter(A, b) : Depuis {0, 1, 2, 4, 7}, une transition 'b' mène à l'état {5}. ε-fermeture({5}) = {1, 2, 4, 5, 6, 7}. C'est notre nouvel état C.

Calcul des transitions depuis B :

• Transiter(B, a) : Depuis {1, 2, 3, 4, 6, 7, 8}, 'a' mène à {3, 8}. ε-fermeture({3, 8}) = {1, 2, 3, 4, 6, 7, 8} = B.
• Transiter(B, b) : Depuis {1, 2, 3, 4, 6, 7, 8}, 'b' mène à {5, 9}. ε-fermeture({5, 9}) = {1, 2, 4, 5, 6, 7, 9}. C'est notre nouvel état D.

Calcul des transitions depuis C :

• Transiter(C, a) : Depuis {1, 2, 4, 5, 6, 7}, 'a' mène à {3, 8}. ε-fermeture({3, 8}) = {1, 2, 3, 4, 6, 7, 8} = B.
• Transiter(C, b) : Depuis {1, 2, 4, 5, 6, 7}, 'b' mène à {5}. ε-fermeture({5}) = {1, 2, 4, 5, 6, 7} = C.

Calcul des transitions depuis D :

• Transiter(D, a) : Depuis {1, 2, 4, 5, 6, 7, 9}, 'a' mène à {3, 8}. ε-fermeture({3, 8}) = {1, 2, 3, 4, 6, 7, 8} = B.
• Transiter(D, b) : Depuis {1, 2, 4, 5, 6, 7, 9}, 'b' mène à {5, 10}. ε-fermeture({5, 10}) = {1, 2, 4, 5, 6, 7, 10}. C'est notre nouvel état E.

Calcul des transitions depuis E :

• Transiter(E, a) : Depuis {1, 2, 4, 5, 6, 7, 10}, 'a' mène à {3, 8}. ε-fermeture({3, 8}) = {1, 2, 3, 4, 6, 7, 8} = B.
• Transiter(E, b) : Depuis {1, 2, 4, 5, 6, 7, 10}, 'b' mène à {5}. ε-fermeture({5}) = {1, 2, 4, 5, 6, 7} = C.

Table de transition finale du DFA : Les états d'acceptation du DFA sont tous ceux contenant l'état d'acceptation 10 du NFA. L'unique état final est donc E.

État DFA	Sous-ensembles d'origine NFA	Symbole 'a'	Symbole 'b'	Final ?
A (Initial)	{0, 1, 2, 4, 7}	B	C	Non
B	{1, 2, 3, 4, 6, 7, 8}	B	D	Non
C	{1, 2, 4, 5, 6, 7}	B	C	Non
D	{1, 2, 4, 5, 6, 7, 9}	B	E	Non
E	{1, 2, 4, 5, 6, 7, 10}	B	C	Oui

Chapitre IV - Les langages à contexte libre

Exercice 1 - Grammaire hors contexte et dérivation

Question : Soit Σ={a, b}, L = {w ∈ Σ*, w contient 2n 'a', n ≥ 1}.

1. Donnez G = (V, Σ, R, S) tel que L(G) = L.
2. Donnez une dérivation gauche de la chaîne w = abaababa ∈ L.
3. Montrer que L(G) = L.

Correction préliminaire sur l'énoncé source : La question 2 demande la dérivation de w = abaababa. Or, si on compte les lettres 'a' dans a b a a b a b a, il y en a 5 (un nombre impair). Ce mot n'appartient pas au langage L (qui requiert un nombre pair de 'a', soit 2n). Le corrigé imprimé dans le document source dérive en réalité le mot w = bbaababa (qui possède 4 lettres 'a', ce qui est valide). Nous corrigerons donc la chaîne étudiée pour appliquer la dérivation gauche sur le mot valide bbaababa défini dans la correction de la source.

Solutions :

1) Définition de la grammaire G : V = {S, A, a, b} Σ = {a, b} Axiome = S Ensemble des règles R : S → AA A → bA A → Ab A → AAA A → a (Logique : 'A' génère toute sous-chaîne contenant un nombre impair de 'a'. 'S' générant 'AA' concatène deux nombres impairs, garantissant un nombre pair (2n) de 'a' dans le mot final).

2) Dérivation gauche du mot w = bbaababa : La dérivation gauche oblige à toujours substituer le symbole non terminal situé le plus à gauche dans la forme sententielle. S ⇒ AA ⇒ bAA (Règle : A → bA sur le 1er A) ⇒ bbAA (Règle : A → bA sur le 1er A) ⇒ bbaA (Règle : A → a sur le 1er A - il est maintenant terminal) ⇒ bbaAAA (Règle : A → AAA sur le A restant) ⇒ bbaAbAA (Règle : A → bA sur le 1er des trois A) ⇒ bbaabAA (Règle : A → a sur ce A) ⇒ bbaabaA (Règle : A → a sur le 2ème des trois A) ⇒ bbaababA (Règle : A → bA sur le dernier A) ⇒ bbaababa (Règle : A → a sur le dernier A)

3) Démonstration que L(G) = L :

• Démonstration L(G) ⊆ L (tout mot généré a un nombre pair de 'a') : Nous le prouvons par récurrence sur la longueur de la dérivation.

  • Base (k=1) : S ⇒ AA. La chaîne contient 2 entités 'A', un nombre pair de variables.
  • Hypothèse : Toute dérivation de longueur k possède un nombre total pair de (A + a).
  • Étape (k=n+1) : Dans la dérivation w_n ⇒ w_n+1, les règles (A → bA, A → Ab, A → a) remplacent un 'A' par un 'A' ou un 'a', le nombre (A+a) ne change pas. La règle (A → AAA) remplace un 'A' par trois 'A', augmentant le total de 2, ce qui conserve la parité. Puisque la forme sententielle terminale n'est constituée que de symboles terminaux, le nombre de 'a' (et 'A'=0) reste pair.

• Démonstration L ⊆ L(G) (tout mot pair est généré par G) : Tout mot w ∈ L possédant 2n occurrences de 'a' peut s'écrire sous la forme générique : w = b^{m1} a b^{m2} a ... b^{m2n} a b^{m2n+1} Dérivation : On utilise l'axiome S ⇒ AA. Ensuite, on dérive l'un des 'A' par A → AAA (répété n-1 fois) pour obtenir exactement 2n variables 'A'. Ensuite, chaque 'A' de## Chapitre I - Alphabet et langages

Exercice 1 - Démonstration par récurrence sur l'image d'un mot (reverse)

Énoncé : Montrer par récurrence que (ωu)R = uR.ωR pour tout entier k tel que |u| = k.

Solution : Nous allons démontrer cette propriété par récurrence sur k, la longueur du mot u.

Cas de base (k = 0) : Si |u| = 0, alors u est le mot vide ε. Calculons le membre de gauche : (ωu)R = (ωε)R = ωR. Calculons le membre de droite : uR.ωR = εR.ωR = ε.ωR = ωR. L'égalité est vérifiée pour k = 0.

Hypothèse de récurrence : On suppose que la propriété est vraie pour un certain entier n ≥ 0. C'est-à-dire que pour tout mot x tel que |x| = n, on a : (ωx)R = xR.ωR.

Hérédité (k = n + 1) : Montrons que la propriété est vraie pour un mot de longueur n + 1. Soit x un mot de longueur n + 1. On peut décomposer x sous la forme x = u.a, où u est un mot de longueur n et a est un symbole de l'alphabet Σ.

Calculons (ωx)R : (ωx)R = (ωua)R

Par définition de l'opération miroir (reverse) sur un mot se terminant par un symbole unique, on a : (ωua)R = a.(ωu)R

En appliquant notre hypothèse de récurrence sur le mot u (puisque |u| = n), on peut remplacer (ωu)R par uR.ωR : a.(ωu)R = a.(uR.ωR)

Puisque la concaténation est associative, on peut regrouper les termes : a.uR.ωR = (a.uR).ωR

Or, par définition du miroir de x = u.a, nous savons que xR = (ua)R = a.uR. En substituant cela dans l'équation : (a.uR).ωR = (ua)R.ωR = xR.ωR

La propriété est donc démontrée pour k = n + 1. Par le principe de récurrence, (ωu)R = uR.ωR pour tout mot u.

Exercice 2 - Propriété de la fermeture de Kleene

Énoncé : Soit Σ = {0,1} et L = { ω ∈ Σ* : ω contient un nombre de 0 différent du nombre de 1 }. Montrez que L* = Σ*.

Solution : Pour démontrer l'égalité L* = Σ*, nous devons prouver la double inclusion : L* ⊆ Σ* et Σ* ⊆ L*.

1. Première inclusion : L ⊆ Σ** Par définition, le langage L est un sous-ensemble de Σ* (les mots de L sont formés sur l'alphabet Σ). La fermeture de Kleene L* est constituée de toutes les concaténations possibles de mots appartenant à L. Puisque la concaténation de mots définis sur Σ donne toujours un mot défini sur Σ, il est évident que L* ⊆ Σ*.

2. Deuxième inclusion : Σ ⊆ L** Il faut démontrer que tout mot w défini sur Σ = {0,1} peut s'écrire comme une concaténation de mots de L. Regardons les symboles de l'alphabet individuellement :

• Le mot "0" contient un '0' et zéro '1'. Puisque 1 ≠ 0, le mot "0" appartient à L.
• Le mot "1" contient zéro '0' et un '1'. Puisque 0 ≠ 1, le mot "1" appartient à L.

Puisque les lettres individuelles '0' et '1' appartiennent toutes deux à L, tout mot w ∈ Σ*, qui est par définition une séquence finie de '0' et de '1', peut être vu comme la concaténation de mots de L de longueur 1. Par conséquent, tout mot de Σ* appartient à L*. Donc Σ* ⊆ L*.

Conclusion : Puisque L* ⊆ Σ* et Σ* ⊆ L*, on en déduit formellement que L* = Σ*.

Chapitre II - Représentation finie des langages

Exercice 1 - Expressions régulières pour des langages spécifiques

Énoncé : Donner les expressions régulières qui génèrent les langages suivants définis sur {a,b}* :

L1 = {w contient exactement bbb} Note : L'énoncé est légèrement ambigu. Il peut signifier soit que le mot est exactement "bbb", soit qu'il contient une seule séquence de trois 'b' consécutifs. Au vu des questions suivantes (L2, L3), la formulation "exactement bbb" désigne le mot lui-même. Expression régulière : bbb

L2 = {w contient la sous chaîne bbb} Il s'agit de n'importe quelle séquence de 'a' et de 'b', suivie de "bbb", suivie de n'importe quelle séquence de 'a' et de 'b'. Expression régulière : (a ∪ b)* bbb (a ∪ b)*

L3 = {w contient seulement 3b, le reste c'est des a's} Le mot contient exactement trois symboles 'b' au total, séparés et entourés par un nombre arbitraire (éventuellement nul) de 'a'. Expression régulière : a* b a* b a* b a*

L4 = {w contient un nombre de a divisible par 3} Le nombre de 'a' doit être un multiple de 3 (0, 3, 6, 9...). Ces blocs de trois 'a' peuvent être entremêlés d'un nombre quelconque de 'b'. Expression régulière : (b* a b* a b* a)* b*

L5 = {w ne contient pas 3b consécutifs} Le mot ne doit jamais contenir la sous-chaîne "bbb". Cela signifie que toute séquence de 'b' est de longueur maximale 2, et doit être suivie d'au moins un 'a' (sauf potentiellement à la toute fin du mot). Expression régulière : (a ∪ ba ∪ bba)* (ε ∪ b ∪ bb)

L6 (première occurrence) = {w contient un nombre impair de b} Le mot doit contenir au moins un 'b' pour être impair. Après cela, on doit s'assurer que les 'b' supplémentaires viennent par paires. Expression régulière : a* b (a ∪ b a* b)*

L6 (seconde occurrence) = {w contient un nombre pair de a} Le nombre de 'a' doit être pair (0, 2, 4...). Les 'a' vont par paires séparées par des 'b'. Le mot peut commencer et finir par n'importe quel nombre de 'b'. Expression régulière : b* (a b* a b*)*

L7 = {w contient la sous chaîne aaa ou la sous chaîne bbb mais pas les deux en même temps} Ce langage est l'union de deux sous-langages :

1. Mots avec "aaa" mais sans "bbb" : L'expression garantissant l'absence de "bbb" est (a ∪ ba ∪ bba)(ε ∪ b ∪ bb). Pour y forcer la présence de "aaa", on réécrit cette base pour injecter un bloc "aaa" : (ε ∪ b ∪ bb) (a ∪ ab ∪ abb) aaa (a ∪ ba ∪ bba)* (ε ∪ b ∪ bb)
2. Mots avec "bbb" mais sans "aaa" : Par symétrie, l'expression est : (ε ∪ a ∪ aa) (b ∪ ba ∪ baa)* bbb (b ∪ ab ∪ aab)* (ε ∪ a ∪ aa)

Expression régulière finale : ((ε ∪ b ∪ bb) (a ∪ ab ∪ abb)* aaa (a ∪ ba ∪ bba)* (ε ∪ b ∪ bb)) ∪ ((ε ∪ a ∪ aa) (b ∪ ba ∪ baa)* bbb (b ∪ ab ∪ aab)* (ε ∪ a ∪ aa))

Chapitre III - Automates à états finis

Exercice - Algorithme de déterminisation NFA vers DFA

Énoncé : Construire le DFA pour le NFA fourni dans la figure (états 0 à 10, transitions sur a, b, et ε).

Solution : Pour convertir un automate fini non déterministe (NFA) en automate fini déterministe (DFA), nous utilisons l'algorithme des sous-ensembles basé sur deux opérations clés :

• ε-fermeture(q) : L'ensemble des états accessibles depuis q par des transitions ε uniquement.
• Transiter(T, a) : L'ensemble des états accessibles depuis l'ensemble d'états T via le symbole d'entrée a.

Étape 1 : État initial du DFA L'état initial A du DFA est la ε-fermeture de l'état initial du NFA (état 0). Depuis 0, par des transitions ε, on peut atteindre 1, 2, 4, et 7. A = ε-fermeture(0) = {0, 1, 2, 4, 7}

Étape 2 : Évaluation des transitions pour chaque nouvel état généré Pour chaque symbole de l'alphabet Σ = {a, b}, on calcule ε-fermeture(Transiter(État, symbole)).

À partir de A = {0, 1, 2, 4, 7} :

• Lecture de 'a' : Seuls les états 2 et 7 ont des transitions sur 'a' (vers 3 et 8). Transiter(A, a) = {3, 8} ε-fermeture({3, 8}) = {1, 2, 3, 4, 6, 7, 8} = B
• Lecture de 'b' : Seul l'état 4 a une transition sur 'b' (vers 5). Transiter(A, b) = {5} ε-fermeture({5}) = {1, 2, 4, 5, 6, 7} = C

À partir de B = {1, 2, 3, 4, 6, 7, 8} :

• Lecture de 'a' : Transitions depuis 2 (vers 3) et 7 (vers 8). Transiter(B, a) = {3, 8} ε-fermeture({3, 8}) = {1, 2, 3, 4, 6, 7, 8} = B
• Lecture de 'b' : Transitions depuis 4 (vers 5) et 8 (vers 9). Transiter(B, b) = {5, 9} ε-fermeture({5, 9}) = {1, 2, 4, 5, 6, 7, 9} = D

À partir de C = {1, 2, 4, 5, 6, 7} :

• Lecture de 'a' : Transitions depuis 2 (vers 3) et 7 (vers 8). Transiter(C, a) = {3, 8} ε-fermeture({3, 8}) = B
• Lecture de 'b' : Transition depuis 4 (vers 5). Transiter(C, b) = {5} ε-fermeture({5}) = C

À partir de D = {1, 2, 4, 5, 6, 7, 9} :

• Lecture de 'a' : Transitions depuis 2 (vers 3) et 7 (vers 8). Transiter(D, a) = {3, 8} ε-fermeture({3, 8}) = B
• Lecture de 'b' : Transitions depuis 4 (vers 5) et 9 (vers 10). Transiter(D, b) = {5, 10} ε-fermeture({5, 10}) = {1, 2, 4, 5, 6, 7, 10} = E

À partir de E = {1, 2, 4, 5, 6, 7, 10} :

• Lecture de 'a' : Transitions depuis 2 (vers 3) et 7 (vers 8). Transiter(E, a) = {3, 8} ε-fermeture({3, 8}) = B
• Lecture de 'b' : Transition depuis 4 (vers 5). L'état 10 n'a pas de sortie sur 'b'. Transiter(E, b) = {5} ε-fermeture({5}) = C

Étape 3 : Identification des états finaux Le NFA a pour état final l'état 10. Tout sous-ensemble du DFA contenant l'état 10 est un état final. Le seul ensemble concerné est E. L'état E est donc l'unique état d'acceptation.

Table de transition du DFA résultant :

État courant	Entrée 'a'	Entrée 'b'	Statut de l'état
A	B	C	Initial
B	B	D
C	B	C
D	B	E
E	B	C	Final

Chapitre IV - Les langages à contexte libre (CFL)

Exercice - Construction et vérification d'une grammaire

Énoncé : Soit L = {w ∈ {a,b}*, w contient 2n symboles 'a', avec n ≥ 1}.

1. Donnez une grammaire G = (V, Σ, R, S) telle que L(G) = L.
2. Donnez une dérivation gauche du mot w = bbaababa ∈ L.
3. Montrez que L(G) = L.

Solution :

1. Définition de la grammaire G : Afin de forcer l'apparition d'un nombre pair de 'a', nous utilisons un non-terminal 'A' qui produit récursivement des 'b' et qui finira toujours par se dériver en générant un 'a'. L'axiome produira deux fois ce non-terminal.

• V = {S, A, a, b}
• Σ = {a, b}
• Axiome = S
• Règles de production R : S → AA A → bA (génère des 'b' à gauche de 'A') A → Ab (génère des 'b' à droite de 'A') A → AAA (permet de multiplier par deux le nombre de 'a' tout en préservant la parité du total) A → a (dérive finalement le non-terminal en un terminal 'a')

2. Dérivation gauche du mot w = bbaababa : Dans une dérivation gauche, on remplace toujours le non-terminal situé le plus à gauche dans la forme sententielle. S ⇒ AA ⇒ bAA (règle A → bA) ⇒ bbAA (règle A → bA) ⇒ bbaA (règle A → a) ⇒ bbaAAA (règle A → AAA) ⇒ bbaAbAA (règle A → bA) ⇒ bbaabAA (règle A → a) ⇒ bbaabaA (règle A → a) ⇒ bbaababA (règle A → bA) ⇒ bbaababa (règle A → a)

3. Preuve que L(G) = L : La preuve d'égalité requiert la démonstration de la double inclusion : L(G) ⊆ L et L ⊆ L(G).

Preuve de L(G) ⊆ L : Nous devons prouver par récurrence sur la longueur de la dérivation que toute forme sententielle (mot contenant potentiellement des non-terminaux) générée à partir de S contient un nombre pair de symboles qui sont soit 'a', soit 'A'.

• Cas de base (k=1) : La dérivation S ⇒ AA donne exactement deux 'A', ce qui est pair.
• Hypothèse : Supposons que pour toute dérivation de longueur k, le nombre total de 'a' et 'A' est pair (2n).
• Récurrence (k+1) : Pour passer de l'étape k à k+1, on dérive un non-terminal 'A' via l'une de ses règles :
  • A → bA : remplace un 'A' par un 'A' (le nombre total de 'a' et 'A' reste inchangé).
  • A → Ab : remplace un 'A' par un 'A' (inchangé).
  • A → a : remplace un 'A' par un 'a' (la somme des 'A' et 'a' reste inchangée).
  • A → AAA : remplace un 'A' par trois 'A' (le total augmente de 2, préservant la parité). Puisque chaque règle conserve la parité, un mot final ne contenant plus que des terminaux aura nécessairement un nombre pair de 'a'. Donc, tout mot généré par G appartient à L.

Preuve de L ⊆ L(G) : Soit un mot générique de L comportant un nombre pair de 'a' (soit 2n). Il peut s'écrire sous la forme : w = (b^m1) a (b^m2) a ... (b^m2n) a (b^m2n+1) Pour obtenir ce mot depuis S, on suit cette procédure :

1. Appliquer S → AA (1 fois).
2. Appliquer la règle A → AAA sur le 'A' de droite, (n-1) fois successives. On obtient une forme sententielle contenant exactement 2n occurrences du non-terminal 'A'.
3. Pour chaque 'A' allant de la gauche vers la droite :
   • Appliquer A → bA autant de fois que nécessaire pour générer les 'b' précédents.
   • Appliquer A → a pour transformer le non-terminal en terminal 'a'.
4. Pour le tout dernier 'A', on peut appliquer A → bA ou A → Ab pour gérer les 'b' terminaux, puis A → a. Toute chaîne de L peut ainsi être dérivée à l'aide des règles de G, ce qui démontre que L ⊆ L(G).

Chapitre V - Automates à pile

Exercice - Construction d'une grammaire pour une union de langages

Énoncé : Construire une grammaire pour le langage L = {a^i b^j c^k, avec (i = j) ou (j = k)}.

Solution : Le langage L est l'union logique de deux langages : L1 = {a^i b^j c^k, avec i = j, k ≥ 0} L2 = {a^i b^j c^k, avec i ≥ 0, j = k}

Nous allons définir une grammaire pour L1, une grammaire pour L2, puis réunir les axiomes sous un nouvel axiome S.

Grammaire pour L1 (i = j) : Dans L1, le nombre de 'a' égale le nombre de 'b'. La séquence de 'c' est totalement indépendante. L1 est donc la concaténation d'une partie {a^i b^i} générée par S1a et d'une partie {c^k} générée par S1b.

• S1 → S1a S1b
• S1a → a S1a b | ε (Génère a^i b^i)
• S1b → c S1b | ε (Génère c^k)

Grammaire pour L2 (j = k) : Dans L2, le nombre de 'b' égale le nombre de 'c'. La séquence de 'a' est indépendante. L2 est la concaténation de {a^i} généré par S2a et de {b^j c^j} généré par S2b.

• S2 → S2a S2b
• S2a → a S2a | ε (Génère a^i)
• S2b → b S2b c | ε (Génère b^j c^j)

Grammaire globale G pour L = L1 ∪ L2 : On introduit un axiome S qui permet de choisir l'une ou l'autre des deux branches.

• V = {S, S1, S1a, S1b, S2, S2a, S2b, a, b, c}
• Σ = {a, b, c}
• Axiome = S
• Règles (R) : S → S1 | S2 S1 → S1a S1b S1a → a S1a b | ε S1b → c S1b | ε S2 → S2a S2b S2a → a S2a | ε S2b → b S2b c | ε

Méthode

Face à une épreuve de théorie des langages et des automates, la structure logique prime sur l'intuition. Voici comment aborder les problèmes :

1. Opérations sur les mots et récurrences : Posez toujours explicitement votre cas de base, votre hypothèse de récurrence (en nommant la variable sur laquelle elle porte), et déroulez l'hérédité en citant les définitions (concaténation, miroir). Ne sautez aucune étape algébrique.
2. Expressions régulières : Traduisez les phrases en contraintes d'exclusion (ce que le mot ne doit pas contenir) ou d'inclusion. Pensez à l'étoile de Kleene * pour représenter le bruit (zéro ou plusieurs occurrences) autour de votre motif central. L'union ∪ est votre outil principal pour les conditions "ou".
3. Déterminisation (NFA vers DFA) : La rigueur de la table de transition est essentielle. Calculez vos ε-fermeture systématiquement. Une simple erreur d'omission d'un état à l'étape 1 se propage en avalanche jusqu'à la fin de l'algorithme. Nommez clairement vos nouveaux états (A, B, C...).
4. Création de Grammaires (CFG) : Identifiez les dépendances. Si deux lettres doivent avoir le même nombre d'occurrences (ex: a^n b^n), elles doivent être générées simultanément de part et d'autre d'un non-terminal central (A → aAb). Si une section est indépendante, confiez-la à un non-terminal distinct.
5. Preuves d'égalité de langages : Abordez toujours la preuve en deux temps (inclusion L1 dans L2, puis L2 dans L1). Utiliser la récurrence sur la longueur de la dérivation est la méthode la plus formelle pour démontrer les propriétés générées par une CFG.