THL TD2

Télécharger au format pdf ou txt
Télécharger au format pdf ou txt
Vous êtes sur la page 1sur 2

UHBC / FSEI Module : THL

Département Informatique Niveau : L2

Fiche de TD N°2
(Langages et Grammaires)

Exercice 1

Soit le mot x = ((acbc)R.baca)R (αR désigne le reflet miroir de α)


1) Donner la chaîne de caractères à laquelle x est égal.
2) Quelle est la valeur de |x|, |x|a, |x|b et |x|c ?
3) Donner un préfixe propre de x contenant au moins deux lettres ‘c’.
4) Donner un suffixe propre de x contenant une seule lettre ‘a’.

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

Soit la grammaire G = ({a, b, c} , {S, A} , S , P) ; où P contient les règles suivantes :


S → aS | bA ; A → cA | ε
1) Déterminer si les mots w1 = abac, w2 = aabccc, w3 = cabbac et w4 = ab sont générés par G.
2) Trouver le langage généré par G ( qu’on note L(G) )

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

Soient les grammaires Gi = ({a, b, c} , {S, A, B, R, T} , S , Pi), (i=1,..,6) ; où les Pi sont :


1) P1 : S → aA | bB ; A → a | ab ; B → b | cb
2) P2 : S → bA ; A → aA | ε
UHBC / FSEI Module : THL
Département Informatique Niveau : L2

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

Soit le langage L défini comme suit :


L = ensemble de tous les mots de {0, 1}* qui contiennent un nombre pair de ‘1’.
1) Montrer que L est de type 3 en trouvant une grammaire de type 3 qui l’engendre.
2) Trouver une grammaire de type 2, et qui n’est pas de type 3, qui engendre L.

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𝐿̅.

Vous aimerez peut-être aussi