TD Automates, langages et applications
TD Automates, langages et applications
Programming, Math, etc. · exam
Fiche de révisionCorrigé
Rédigée à partir de ce document, puis vérifiée avant publication.
Ce document présente un ensemble d'exercices corrigés en grammaires formelles, issus d'un TD sur les automates, langages et applications. Il vise à tester les compétences en construction, analyse, simplification et ambiguïté des grammaires, ainsi que l'application d'algorithmes comme CYK.
Construire la grammaire générant tous les palindromes sur l’alphabet {0, 1}.
Une grammaire générant tous les palindromes sur {0,1} doit permettre de construire des mots qui se lisent de la même façon de gauche à droite et de droite à gauche.
On peut définir la grammaire suivante :
S → 0 | 1 | ε | 0S0 | 1S1
Explication :
- ε est le palindrome vide.
- 0 et 1 sont des palindromes de longueur 1.
- 0S0 et 1S1 ajoutent un même symbole aux deux extrémités, garantissant la symétrie.
Réponse : La grammaire S → 0 | 1 | ε | 0S0 | 1S1 génère tous les palindromes sur {0,1}.
Soit la grammaire :
S → (L) | a
L → L,S | S
1. Identifier les symboles terminaux et non terminaux.
Les symboles non terminaux sont : S, L.
Les symboles terminaux sont : a, (, ), , (la virgule).
2. Donner les arbres de dérivation pour :
3. Construire une dérivation à gauche et une dérivation à droite pour chacune des phrases ci-dessus.
Travail :
Dérivation à gauche :
S ⇒ (L) ⇒ (L,S) ⇒ (S,S) ⇒ (a,S) ⇒ (a,a)
Dérivation à droite :
S ⇒ (L) ⇒ (L,S) ⇒ (L,a) ⇒ (S,a) ⇒ (a,a)
Dérivation à gauche :
S ⇒ (L) ⇒ (L,S) ⇒ (S,S) ⇒ (a,S) ⇒ (a,(L)) ⇒ (a,(L,S)) ⇒ (a,(S,S)) ⇒ (a,(a,S)) ⇒ (a,(a,a))
Dérivation à droite :
S ⇒ (L) ⇒ (L,S) ⇒ (L,(L)) ⇒ (L,(L,S)) ⇒ (L,(L,a)) ⇒ (L,(S,a)) ⇒ (L,(a,a)) ⇒ (S,(a,a)) ⇒ (a,(a,a))
Dérivation à gauche :
S ⇒ (L) ⇒ (L,S) ⇒ (S,S) ⇒ (a,S) ⇒ (a,(L)) ⇒ (a,(L,S)) ⇒ (a,(S,S)) ⇒ (a,((L),S)) ⇒ (a,((L,S),S)) ⇒ (a,((S,S),S)) ⇒ (a,((a,S),S)) ⇒ (a,((a,a),S)) ⇒ (a,((a,a),(L))) ⇒ (a,((a,a),(L,S))) ⇒ (a,((a,a),(S,S))) ⇒ (a,((a,a),(a,S))) ⇒ (a,((a,a),(a,a)))
Dérivation à droite :
S ⇒ (L) ⇒ (L,S) ⇒ (L,(L)) ⇒ (L,(L,S)) ⇒ (L,(L,(L))) ⇒ (L,(L,(L,S))) ⇒ (L,(L,(L,a))) ⇒ (L,(L,(S,a))) ⇒ (L,(L,(a,a))) ⇒ (L,(S,(a,a))) ⇒ (L,((L),(a,a))) ⇒ (L,((L,S),(a,a))) ⇒ (L,((L,a),(a,a))) ⇒ (L,((S,a),(a,a))) ⇒ (L,((a,a),(a,a))) ⇒ (S,((a,a),(a,a))) ⇒ (a,((a,a),(a,a)))
Réponse : Les dérivations et arbres ci-dessus correspondent aux phrases demandées.
Soit la grammaire :
S → aB | bA
A → a | aS | bAA
B → b | bS | aBB
1. Trouver pour le mot aaabbabbba une dérivation à gauche, une dérivation à droite et un arbre de dérivation.
2. Montrer par récurrence sur |w| que L(G) est l’ensemble des mots de longueur non nulle qui contiennent autant de a que de b.
Travail :
1. Dérivation à gauche :
S ⇒ aB ⇒ aaBB ⇒ aaaBBB ⇒ aaabBB ⇒ aaaabbB ⇒ aaabbaBB ⇒ aaabbabB ⇒ aaabbabbS ⇒ aaabbabbbA ⇒ aaabbabbba
Dérivation à droite :
S ⇒ aB ⇒ aaBB ⇒ aaBbS ⇒ aaBbbA ⇒ aaBbba ⇒ aaaBBbba ⇒ aaaBbbba ⇒ aaabSbbba ⇒ aaabbAbbba ⇒ aaabbabbba
Ces deux dérivations produisent des arbres différents.
Arbre de dérivation :
Représentation d'un arbre avec S en racine, branches vers a, B, puis développement récursif selon la dérivation.
2. Preuve par récurrence :
Définissons :
On montre que :
Base : |w|=1
Pour |w|=2, si w ∈ L0 alors w = ab ou ba, et S dérive ces mots.
Hypothèse : pour tout mot de longueur inférieure à n, propriété vraie.
Pour w de longueur n, si S ⇒* w, alors S ⇒ aB ⇒* w ou S ⇒ bA ⇒* w. Dans le premier cas, B ⇒* w' avec |w'| < n et w = a w' ∈ L0. Dans le second cas, A ⇒* w' avec |w'| < n et w = b w' ∈ L0.
Inversement, si w ∈ L0, alors w commence par a ou b, et on applique la même logique pour montrer la dérivabilité.
Réponse : Le langage L(G) est exactement l'ensemble des mots non vides contenant autant de a que de b.
Quel est le langage reconnu par la grammaire :
S → AB | C
A → aAb | ab
B → cBd | cd
C → aCd | aDd
D → bDc | bc
Analyse :
Réponse : Le langage reconnu est {aⁿbⁿcᵐdᵐ} ∪ {aⁿbᵐcᵐdⁿ} pour n,m ≥ 1.
Montrer que la grammaire suivante génère tous les mots de parenthèses équilibrées et corrects :
S → (S)S | ε
1. Montrons que tous les mots générés sont corrects :
2. Montrons que tous les mots corrects sont générés :
Réponse : La grammaire S → (S)S | ε génère exactement tous les mots de parenthèses équilibrées et corrects.
Soit la grammaire :
S → aSbS | bSaS | ε
Montrer que cette grammaire est ambiguë en générant deux dérivations à gauche pour abab. Donner deux dérivations à droite de abab. Quels sont les arbres de dérivation correspondants ?
Travail :
Dérivations à gauche :
S ⇒ aSbS ⇒ abS ⇒ abaSbS ⇒ ababS ⇒ abab
S ⇒ aSbS ⇒ abSaSbS ⇒ abaSbS ⇒ ababS ⇒ abab
Dérivations à droite :
S ⇒ aSbS ⇒ aSbaSbS ⇒ aSbaSb ⇒ aSbab ⇒ abab
S ⇒ aSbS ⇒ aSb ⇒ abSaSb ⇒ abSab ⇒ abab
Les arbres de dérivation correspondent à ces différentes façons de décomposer le mot abab, illustrant l'ambiguïté.
Réponse : La grammaire est ambiguë car abab admet au moins deux dérivations à gauche et deux dérivations à droite distinctes, avec des arbres différents.
Soit la grammaire :
R → R|R | RR | R* | (R) | a | b
1. Montrer que cette grammaire génère les expressions régulières sur {a,b}.
2. Montrer que cette grammaire est ambiguë.
3. Construire une grammaire équivalente non ambiguë avec les priorités classiques (∗ puis . puis |) et l’associativité à gauche.
4. Construire un arbre de dérivation pour a|b*b dans les deux grammaires.
Travail :
1. Cette grammaire permet de construire :
Elle génère donc toutes les expressions régulières sur {a,b}.
2. Ambiguïté :
Par exemple, pour a|b*, on a deux dérivations à gauche :
R ⇒ R|R ⇒ a|R ⇒ a|R* ⇒ a|b*
R ⇒ R* ⇒ R|R* ⇒ a|R* ⇒ a|b*
Donc la grammaire est ambiguë.
3. Grammaire non ambiguë avec priorités :
R → R | T | T
T → T F | F
F → F * | a | b | (R)où :
4. Arbres de dérivation pour a|b*b :
Dans la grammaire ambiguë, plusieurs arbres possibles.
Dans la grammaire non ambiguë, l’arbre respecte la priorité * avant | :
Réponse : La grammaire initiale génère toutes les expressions régulières mais est ambiguë. La grammaire proposée avec R, T, F est non ambiguë et respecte les priorités classiques.
Reprenons la grammaire de l’exercice 4 :
S → AB | C
A → aAb | ab
B → cBd | cd
C → aCd | aDd
D → bDc | bc
Montrer que cette grammaire est ambiguë.
Travail :
Le langage est ambigu car si n = m, les mots aⁿbⁿcᵐdᵐ et aⁿbᵐcᵐdⁿ sont identiques.
Par exemple, le mot abcd peut être dérivé de deux façons :
S → AB → abB → abcd
S → C → aDd → abcd
Réponse : La grammaire est ambiguë car certains mots ont plusieurs dérivations distinctes.
Considérons la grammaire :
S → aS | bS | bA
A → bA | b
1. Montrer que cette grammaire est ambiguë en produisant tous les arbres de dérivation pour le mot aabbbb.
2. En assignant des probabilités aux règles, déterminer la dérivation la plus probable pour aabbbb.
Travail :
1. Dérivations possibles :
S → aS → aaS → aabS → aabbS → aabbbA → aabbbb
S → aS → aaS → aabS → aabbA → aabbbA → aabbbb
S → aS → aaS → aabA → aabbA → aabbbA → aabbbb
2. Probabilités assignées :
Calcul des probabilités :
Réponse : La troisième dérivation est la plus probable selon les probabilités données.
Supprimer les symboles inutiles de la grammaire :
S → aAAB | CC | cA
A → aA | a
C → cC
Travail :
Étape 1 : Identifier les symboles qui dérivent un terminal ou une phrase terminale.
Étape 2 : On garde donc :
S → cA
A → aA | a
Réponse : La grammaire simplifiée sans symboles inutiles est :
S → cA
A → aA | a
Supprimer les ε-productions de la grammaire :
S → AB
A → aA | ε
B → b | ε
Travail :
A et B sont annulables (peuvent dériver ε), donc S est aussi annulable.
On remplace :
Pour A :
Pour B :
Réponse : La grammaire sans ε-productions est :
S → AB | A | B | ε
A → aA | a
B → b
Supprimer les règles unitaires de la grammaire :
S → ABc
A → B
B → B | b | c
Travail :
Les règles non unitaires sont S → ABc et B → b | c.
A → B est une règle unitaire. Comme B → b | c, on remplace A → B par A → b | c.
Réponse : La grammaire sans règles unitaires est :
S → ABc
A → b | c
B → b | c
Transformer la grammaire suivante en une grammaire équivalente sans ε, sans symboles inutiles, sans ε-productions et sans règles unitaires :
S → AB | CA
A → a | b | ε
B → BC | DB
C → E | ε
D → a | d
E → aB | c | d | ε
Travail :
S → CA
A → a | b | ε
C → E | ε
D → a | d
E → c | d | ε
S → CA | C | A
A → a | b
C → E
E → c | d
S → CA | a | b | c | d
A → a | b
C → c | d
E → c | d
S → CA | a | b | c | d
A → a | b
C → c | d
Réponse : La grammaire équivalente finale est :
S → CA | a | b | c | d
A → a | b
C → c | d
Grammaire des expressions arithmétiques bien formées :
S → T + S | S + T | T
T → F * T | T * F | F
F → n | (S)
1. Mettre cette grammaire sous forme normale de Chomsky.
2. Utiliser l’algorithme CYK pour déterminer si le mot n+(n) est généré.
Travail :
1. Élimination des ε-productions, règles unitaires et symboles inutiles :
S → T + S | S + T | F * T | T * F | n | (S)
T → F * T | T * F | n | (S)
F → n | (S)
2. Mise en forme normale de Chomsky :
S → T O1 S | S O1 T | F O2 T | T O2 F | n | P1 S P2
T → F O2 T | T O2 F | n | P1 S P2
F → n | P1 S P2
O1 → +
O2 → *
P1 → (
P2 → )
S → T X1 | S X2 | F X3 | T X4 | n | P1 X5
T → F X3 | T X4 | n | P1 X5
F → n | P1 X5
X1 → O1 S
X2 → O1 T
X3 → O2 T
X4 → O2 F
X5 → S P2
3. Application de l’algorithme CYK pour le mot n+(n) :
| Position | 1 (n) | 2 (+) | 3 (() | 4 (n) | 5 ()) |
|---|---|---|---|---|---|
| 1 | {S, T, F} | ∅ | ∅ | ∅ | ∅ |
| 2 | ∅ | {O1, O2} | ∅ | ∅ | ∅ |
| 3 | ∅ | ∅ | {S, T, F, P1} | ∅ | ∅ |
| 4 | ∅ | ∅ | ∅ | {S, T, F} | ∅ |
| 5 | ∅ | ∅ | ∅ | ∅ | {P2} |
Conclusion : Le mot n+(n) est généré par la grammaire car S apparaît dans la case couvrant tout le mot.
Réponse : La grammaire mise en forme normale de Chomsky permet de reconnaître n+(n) via CYK.
Ce TD récompense la maîtrise des techniques suivantes :
Les erreurs pénalisées sont notamment :
La rigueur dans la présentation des étapes et la clarté des raisonnements sont essentielles pour réussir ce type d’exercice.