TD Automates, langages et applications

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.

Exercice 1

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}.

Exercice 2

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 :

• (a,a)
• (a,(a,a))
• (a,((a,a),(a,a)))

3. Construire une dérivation à gauche et une dérivation à droite pour chacune des phrases ci-dessus.

Travail :

• Pour (a,a) :

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)

• Pour (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))

• Pour (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.

Exercice 3

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 :

• L0 : mots de longueur non nulle avec autant de a que de b.
• La : mots avec un a de plus que de b.
• Lb : mots avec un b de plus que de a.

On montre que :

• (S ⇒* w) ⇔ w ∈ L0
• (A ⇒* w) ⇔ w ∈ La
• (B ⇒* w) ⇔ w ∈ Lb

Base : |w|=1

• w ∈ La ⇔ w = a ⇔ A ⇒* a
• w ∈ Lb ⇔ w = b ⇔ B ⇒* b

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.

Exercice 4

Quel est le langage reconnu par la grammaire :

S → AB | C
A → aAb | ab
B → cBd | cd
C → aCd | aDd
D → bDc | bc

Analyse :

• Si on utilise S → AB, on génère d'abord autant de a que de b (via A), puis autant de c que de d (via B). Le langage est donc {aⁿbⁿcᵐdᵐ} avec n,m ≥ 1.
• Si on utilise S → C, on génère d'abord autant de a que de d (via C), puis autant de b que de c (via D). Le langage est donc {aⁿbᵐcᵐdⁿ} avec n,m ≥ 1.

Réponse : Le langage reconnu est {aⁿbⁿcᵐdᵐ} ∪ {aⁿbᵐcᵐdⁿ} pour n,m ≥ 1.

Exercice 5

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 :

• Base : S ⇒ ε est correct.
• Hypothèse : pour une dérivation de longueur n, les mots dérivés sont corrects.
• Pour une dérivation de longueur n+1 : S ⇒ (S)S ⇒ (x)y où x et y sont dérivés de S en moins de n étapes, donc corrects. La concaténation (x)y est donc correcte.

2. Montrons que tous les mots corrects sont générés :

• Base : ε est généré.
• Soit un mot correct w de longueur 2n > 0. Il commence par '('. Soit (x) le plus petit préfixe équilibré, donc w = (x)y avec x,y corrects et de longueur < 2n.
• Par hypothèse, x et y sont générés par S. Donc S ⇒ (S)S ⇒ (x)y = w.

Réponse : La grammaire S → (S)S | ε génère exactement tous les mots de parenthèses équilibrées et corrects.

Exercice 6

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.

Exercice 7

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 :

• Alternation : R → R|R
• Concaténation : R → RR
• Étoile : R → R*
• Parenthèses : R → (R)
• Symboles de base : a, b

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ù :

• R gère l’alternation (|)
• T gère la concaténation
• F gère l’étoile, les symboles et les parenthèses

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 | :

• Le sous-arbre b* est construit en F → F*.
• La concaténation b*b est construite en T → T F.
• L’alternation a|b*b est construite en R → R | T.

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.

Exercice 8

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.

Exercice 9

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 :

• S → aS : 0,8
• S → bS : 0,01
• S → bA : 0,19
• A → bA : 0,9
• A → b : 0,1

Calcul des probabilités :

• 1ère dérivation : 0,8 × 0,8 × 0,01 × 0,01 × 0,19 × 0,1 = valeur faible
• 2ème dérivation : 0,8 × 0,8 × 0,01 × 0,19 × 0,9 × 0,1 = plus élevée
• 3ème dérivation : 0,8 × 0,8 × 0,19 × 0,9 × 0,9 × 0,1 = la plus élevée

Réponse : La troisième dérivation est la plus probable selon les probabilités données.

Exercice 10

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.

• A dérive aA ou a, donc A est utile.
• C dérive cC, mais ne dérive jamais un terminal seul, donc C est inutile.
• S → cA est utile car A est utile.

É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

Exercice 11

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 :

• S → AB
• S → A (B absent)
• S → B (A absent)
• S → ε (A et B absents)

Pour A :

• A → aA | a (ε supprimé)

Pour B :

• B → b (ε supprimé)

Réponse : La grammaire sans ε-productions est :

S → AB | A | B | ε
A → aA | a
B → b

Exercice 12

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

Exercice 13

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 :

1. Élimination des symboles inutiles :
• B ne dérive pas de terminal ou phrase terminale, on l’élimine.
• On obtient :

S → CA
A → a | b | ε
C → E | ε
D → a | d
E → c | d | ε

2. Élimination des ε-productions :
• A, C, E et S sont annulables.
• On obtient :

S → CA | C | A
A → a | b
C → E
E → c | d

3. Élimination des règles unitaires :
• Règles unitaires : S → C, S → A, C → E.
• On remplace par :

S → CA | a | b | c | d
A → a | b
C → c | d
E → c | d

4. Suppression des symboles inutiles :
• E ne dérive pas de S, on l’élimine.
• Grammaire finale :

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

Exercice 14

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 :

• Pas de ε-productions.
• Élimination des règles unitaires :

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 :

• Remplacement des terminaux dans les règles longues :

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 → )

• Scinder les règles longues :

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.

Méthode

Ce TD récompense la maîtrise des techniques suivantes :

• Construction de grammaires générant des langages spécifiques (palindromes, parenthèses équilibrées).
• Analyse de grammaires : identification des symboles terminaux/non terminaux, dérivations à gauche et à droite, arbres de dérivation.
• Preuves par récurrence pour caractériser des langages générés.
• Détection et démonstration d’ambiguïté dans les grammaires, par construction de dérivations multiples.
• Transformation de grammaires : suppression des symboles inutiles, ε-productions, règles unitaires.
• Mise en forme normale de Chomsky et application de l’algorithme CYK pour la reconnaissance de mots.

Les erreurs pénalisées sont notamment :

• Confusion entre symboles terminaux et non terminaux.
• Omission des étapes intermédiaires dans les dérivations.
• Manque de justification dans les preuves par récurrence.
• Ignorer les règles définies dans l’énoncé pour les transformations de grammaires.
• Ne pas vérifier la cohérence des dérivations avec le langage attendu.
• Ne pas appliquer correctement la forme normale de Chomsky ou l’algorithme CYK.

La rigueur dans la présentation des étapes et la clarté des raisonnements sont essentielles pour réussir ce type d’exercice.