U NIVERSITÉ DE T UNIS E L M ANAR 2018-2019
FACULTÉ DES S CIENCES DE T UNIS
————
D ÉPARTEMENT DES S CIENCES DE
L’I NFORMATIQUE
T HÉORIE DES L ANGAGES ET C ALCULABILITÉ (TLC)
T.D.N◦ 3
Les Grammaires
Section : IF4
Enseignantes : Yousra Hlaoui et Faten Abbes
Exercice 1
Soit G la grammaire non contextuelle suivante : ({S, A, B, C, D}, {a, b, c}, R, S) où R contient
les productions suivantes :
S → AB|CD A → aAb|ab B → cB|c C → aC|a D → bDc|bc
1. Construire une dérivation gauche de aabbc et dessiner l’arbre de dérivation associé.
2. Construire une dérivation droite de aabbc et dessiner l’arbre de dérivation associé.
3. Quel est le langage L générée par G ? Justifier votre réponse.
4. Montrer que G est ambigue.
5. Construire G’ telle que L(G0 ) = (L(G))∗ .
6. Construire G" telle que L(G”) = L(G) + ε
Exercice 2
Pour chaque langage non contextuel, proposer une grammaire qui génère ses mots. Dire
si la grammaire proposée est ambiguë ou non. Préciser le type de langage en question en
justifiant votre réponse. Dans le cas où le langage est régulier proposer une grammaire ré-
gulière qui le génère.
1. L1 = {ω ∈ {a, b}∗ /ω = an bn ; n ≥ 0}
2. L2 = {ω ∈ {a, b}∗ /ω = an bn ; n ≥ 0, m ≥ 0, n ≥ m}
3. L3 = {ω ∈ {a, b}∗ /|ω|a = |ω|b }
4. L4 = {ω ∈ {a, b}∗ /ω = ω R } où ω R est l’image miroir de ω
5. L5 = {ω ∈ {a, b}∗ /ω = ω1 ω1R }
1
Exercice 3
Soit G la grammaire suivante : G = ({S, T, L}, {a, b, c, +, −, ×, /, [, ]}, P, S) où P est formé
des productions suivantes :
S → T + S S → T − S S → T T → L × T T → L/T
T → L L → [S] L → a L → b L → c
1. Construire une dérivation gauche de a + a + a.
2. Construire une dérivation gauche de a + b × c
3. Décrire informellement ce que représente L(G).
4. Est ce que G est ambiguë ?
5. Transformer G en G0 telle que : L(G0 ) = L(G) + ε
Exercice 4
Transformer la grammaire suivante G = (V, X, P, S) en une grammaire équivalente G0
exprimée dans la forme normale de CHOMSKY, où :
V = {S, A, B}, X = {a, b} et P = {S → aA, S → bB, A → Baa, A → ba, B → bAA, B → ab}
Exercice 5
Soit G la grammaire définie par : G = {{S, A, B}, {a, b}, {S → ε, A → abaS, S → bA, S →
aB, B → babS}, S}.
Montrer que L(G) = (baba|abab)∗
Exercice 6
Considérer la grammaire G définie par l’ensemble des règles suivant :
S → XaaX X → aX X → bX X→ε
1. G est elle régulière ?
2. Décrire L(G) par une propriété
3. Pourquoi L(G) est un langage régulier ?
4. Proposer une expression régulière R pour L(G)
5. À partir de R donner le AFN M (algorithme vu en cours) tel que L(M ) = L(R)
6. Déduire le AFD M 0 tel que L(M ) = L(M 0 ). Faite la minimisation de M 0
7. Déduire à partir du DFA obtenu une grammaire régulière pour L(G)
