Scribd
Importer
816 vues2 pages

THL TD2

Ce document contient 9 exercices portant sur les langages formels et les grammaires. Les exercices couvrent des sujets comme les propriétés des mots, les opérations sur les langages, et la caractérisation de langages au moyen de grammaires.

Transféré par

DaoudiZahia
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
816 vues2 pages

THL TD2

Ce document contient 9 exercices portant sur les langages formels et les grammaires. Les exercices couvrent des sujets comme les propriétés des mots, les opérations sur les langages, et la caractérisation de langages au moyen de grammaires.

Transféré par

DaoudiZahia
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
Vous êtes sur la page 1/ 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