Université de Batna Module : Théorie des langages
Faculté des sciences
Département d’informatique
TD N°01
Les langages
Exercice n°01
Donner les types des grammaires suivantes:
1. G1=({a,b},{S,A},S,R) où R: S→aA, A→bA
2. G2=({a},{S,A},S,R) où R: S→aA/ ε, A→aA
3. G3=({a},{S,A},S,R) où R: S→aA/a, A→Sa
4. G4=({a,b},{S},S,R) où R: S→aSb/ab
5. G5=({a,b},{S,A},S,R) où R: S→aAb/a, A→bSa
6. G6=({a,b},{S,A},S,R) où R: S→aA, Aa→aSb
7. G7=({a,b},{S,A},S,R) où R: S→A/a, aAb→S
8. G8=({a,b,c},{S,A,B,C,D,E,F},S,R) où R: S→ABC/cD, A→BB/ ε, B→CC/a,
C→AA/b, D→EA, F→bcAB/bc
9. G9=({a,b},{S},S,R) où R: S→babbS/babb/a
10. G10=({a,b},{S,A,B},S,R) où R: S→Ba/Ab, A→Sa/AAb/a, B→Sb/BBa/b
Exercice n°02
1. Soit G1 = ({a, b, c}, {S}, S, {S → aS / Sb / c ; aSb → Sa / bS})
Donner la suite de dérivations permettant de générer la chaine abbcbba.
2. Soit G2 = ({a, b}, {S, T}, S, {S → ab / aTSb / b; T → bSb / ε}).
Montrer que le mot ababbabbb ∈ L(G).
3. Soit G3 = ({a, b}, {S, A}, S, {S → SA / A ; A → a / b / ε}).
Les mots ε, aaaab et a2b3a appartiennent-ils à L(G) ?
4. Soit G4 = ({0, 1}, {S, A}, S, R). R = {S → 0A1 ; 0A → 00A1 ; A → ε}
Les chaines ε, 00111 et 00001111 appartiennent-elles à L(G) ?
5. Soit G5 = ({(,)}, {S, A}, S, R). R = {S → SS ; S → (S)/ε}
Les chaines ((( ))), (( )( )), (( ))( )( ) appartiennent-elles à L(G) ?
Exercice n°03
Donner les langages engendrés par les grammaires suivantes:
1. G = ({a, b}, {S, A}, S, {S → SA / A ; A → a / b / ε}).
2. G = ({0, 1}, {S, A}, S, R); R = {S → 0A1 ; 0A → 00A1 ; A → ε}
3. G = ({a, b}, {S, A, B}, S, R); R = {S → aA ; A → aA / bB ; B → b}
4. G2 = ({a, b, c}, {S, A, B, C}, S, R); R = {S → ABC; A → aA / bA / ε; B → aB
/bB /ε ; C → cC / ε}
5. G3 = ({a, b, c}, {S, R, T}, S, R); R = {S → aRbc / abc; R → aRTb / aTb ; Tb
→ bT; Tc → cc }
1/2
Exercice n°04
Donner les grammaires générant les langages suivants:
1. L1 = {wa|w| / w ∈ {a, b}+}.
2. L2 = {wcwR / w ∈ {a, b}*}.
3. L3 = { w ∈ {a, b}* / |w| n’est pas un multiple de 3}.
4. L4 = { w ∈ {a, b}* / w = anbm et n ≠ m}.
5. L5 = {w ∈ {0, 1}* / |w| = 2p + 1 et p ≥ 0}.
Exercice n°05
Donner les types des langages suivants:
1. L1 = { anbm ck ; n, m, k ≥ 0}.
2. L2 = { anbm ck ; n= m+ k}.
3. L3 = { anbm ck ; n>m+ k}.
4. L4 = { anbm cm d3n ; n, m ≥ 0}.
5. L5 = { anbn cn ; n ≥1}.
6. L6 = { ambm ; m ≥0}.
7. L7 = {w ∈ {a, b}* / |w| = 2k et k ≥ 0}
8. L8 = {w ∈ {0, 1, 2}* / w = 0(1212)∗1p+1 2p 0}
9. L9 = {xnayn / n ≥ 0} U {xnbyn / n ≥ 0}
10. L10 = {a2n / n ≥ 0}
Exercice n°05
a) Donner des grammaires de types différents pour le langage vide (L(G)=ɸ)
b) Soit G = ({0, 1}, {S, A, B}, S, R).
R = {S → 0A0 /1B1;
A → 0A0 / ε;
B → 1B1 / ε}
1. Donner le type de G ?
2. Donner L(G) ? Donner le type de L(G) ?
c) Soit la grammaire G = ({a, b, c, d}, {S, W, X, Y, Z}, S, R).
R = {S → WY / X; W → aWb/ab; X → aXb/Z; Y → cYd /cd; Z → bZc /bc}
1. Donner le type de G ?
2. Donner L(G) le langage engendré par la grammaire G ? Donner le type de
L(G) ?
2/2
