THL TD2
THL TD2
THL TD2
Fiche de TD N°2
(Langages et Grammaires)
Exercice 1
Exercice 2
On définit le mot miroir d’un mot w de V*, par récurrence sur la longueur de w, comme suit :
Si w = ε alors 𝑤 𝑅 = ε ; sinon, il existe a ∈ V et v ∈ 𝑉 ∗ tels que w = a.v, dans ce cas : 𝑤 𝑅 = 𝑉 𝑅 .a.
Démontrer que pour tous u, v, w ∈ 𝑉 ∗ , on a : (u.v)R = vR.uR et (wR)R = w.
Exercice 3
Soient les langages L1 = {a, ab, ba}, L2 = {ε, b, ab} et L3 = {an.bn / n ≥ 0}.
Définir les langages suivants :
a) L1.L2 ; b) L2.L1 ; c) L1.L3 ; d) L1.{ε} ; e) {ε}.L1 ; f) L1.Ø ; g) Ø.L1 ; h) L1.L1 ; i) L2.L2 ; j) L3.L3.
Exercice 4
Exercice 5
Pour chacun des langages suivants, donner des exemples de mots contenus dans chacun des langages, et
des grammaires qui engendrent chacun des langages (Li)i=1,..,5 :
1) L1 = { w ∈ {a, b, c}* / w commence par la lettre ‘a’ }
2) L2 = { w ∈ {a, b, c}* / w se termine par la lettre ‘a’ } ;
3) L3 = { w ∈ {a, b, c}* / w contient au moins une occurrence de la lettre ‘a’ } ;
4) L4 = { w ∈ {a, b, c}* / w contient au moins deux occurrences la lettre ‘a’ } ;
5) L5 = { w ∈ {a, b, c}* / w contient au moins deux occurrences consécutives de la lettre ‘a’ }.
Exercice 6
3) P3 : S → aSc | A ; A → bA | b
4) P4 : S → aSbS | ε
5) P5 : S → aRbc | abc ; R → aRTb | aTb ; Tb → bT ; Tc → cc
6) P6 : S → aAb | ε A → aSb ; Ab → ε
I) Pour chacune des grammaires Gi (i=1,..,6) ; donner le type de celle-ci, puis trouver le langage engendré
par chacune d’elles.
II) Vérifier que G2 n’est pas de type 1 ; mais que L(G2) est de type 1.
III) Montrer que L(G6) est de type 2 en trouvant une grammaire de type 2 qui l’engendre.
Exercice 7
Pour chacun des langages suivants, donner une grammaire qui l’engendre :
L1 = { 02n / n ≥ 0 }
L2 = { 0n 1n / n ≥ 0 }
L3 = { an b2n / n ≥ 0 }
L4 = { an bm cn-m / n ≥ m ≥ 0 }
L5 = {palindromes de {a, b}*}
L6 = complémentaire de L5 (i.e {a, b}*- L5)
L7 = { w {a, b}* / |w| ≡ 0[3] }
L8 = { 0i 1j / i ≥ j ≥ 0 }
L9 = { 0i 1j / i ≠ j, i ≥ 0, j ≥ 0 }
L10 = { a2n / n ≥ 0 }
Exercise 8
Exercice 9
Soit L l’ensemble des mots palindromes construits sur l’alphabet {a, b}, et 𝐿̅ son complémentaire.
1) Les mots suivants sont-ils dans L ? Il s’agit de : abbab, baab, aaab, aba.
2) Donner une grammaire, de type 2, qui génère L.
3) Caractériser les mots du langage𝐿̅.
4) Trouver une grammaire, de type 2, qui génère𝐿̅.