Université de Bejaia

Faculté des sciences exactes 2 année License

Année 2015/2016
Département d'Informatique Module: Théorie des Langages

Epreuve de Moyenne Durée

Nom
Prénom: Groupe

Exercice 1: (8 points)
Soient Ll et L2 deux
langages réguliers tel que: L1 =
(a + b)' et L2 est reconnu par l'AEF (A2) suivant

b b

a
b b

1. Trouver l'AEF (A1) qui reconnait L1 et P'expression régulière qui dénote le langage reconnu par A2.
A1
L2=

2. Calculer L2 || b, L2 || ba, puis L1 || a et L1 l ab

L2 I b=
L2 I bb =

L1 l a =
L1 l ab =

« La confiance en soi est le premier secret du succes Ralph »

Waldo Emerson
 3. Déduire des AEFs qui reconnaissent 11 || ab et de L2 I b

4. Calculer L3 = (L1UL2) ib, puis trouver un AEF (A3) simple reconnaissant le langagel3.

L3= A3

Exercice 2: (8 points)
Soient L1, L2, L3, et L4 quatre langages tel que:

L1 ={(dd) b ' , tq i > 0 etj > 1}, L2 ={(dd)'b"¢7=i, tq n 2 i 2 0}, L3 ={d2ib' c', tq i> O etj s i) et la
fonction de transition (o ) de l'automate qui reconnais L4 est définie comme suit

1. o( d, qo, d) = (dd, q0) 5. o(20.q2, b) = (zo, q2)

2. olz0,90, d) = (Z0d, qo) 6. ald, 92, b) = (e, q1)

3. o(d, 9o, b) = (E, 91) 7.

o(z0.2,E) =
(Z0» 9finai)
4. a(d, q1, b) = (E, 92)

1. Trouver les paramètres de l'automate qui reconnait L4: (ne pas réécrire la fonction de transition)

2. les mots: dbb, db, ddb et ddbb appartiennent ils à L4 ? (justifiez votre réponse)

La confiance en soi est le premiersecret du succès» Ralph Waldo Emerson

 Trouver le langage L4. L4

.rouver une
grammaire 61 de type 3 qui génère L1, une
63 de type 0 grammaire G2 de type 2 qui génère L2 et une grammaire
qui génère L3. (Ne donner que les
règles de production)
G3
G2
G1

5. Calculer LinL, puis trouver

l'automate adéquat correspondant.
L1nL2=

aLo confionce en sOi est le premlersecret du succes » Ralolh Walda tinerson

 que: (L1n L2).
L = L3 (si. oui trouver L, Slo
.
Peut on trouver un langage L de tvpe 3, tel

n L2).L L4 (si oui trouver L, sinon justifier)

Peut on trouver un langage lL de type 3, tel que: (L1
=

Exercice 3: (4 points)

Soient G1(T, N1, S), G2(T, N2, S) et G3(T, N3, S)

suivantes: (T =
{a,c, b})

G1: S cA/ cb G2 S cAS/ CC G3: ScSBa /cSB / cS/ E

Ccb aBBa
A Sb
Avec N1 ={S,A} AC C cBch
Avec N1 {S,A, C}
Avec N1 = {S, B, C}, et

y e(TUN
L2, les langages gênérés par les grammaires G1 et Gl respectivement
1. Trouver L1et

L1
L2

et L3
2. Quel est le type de L1,L2

Type de L2 . .*****'************** Type de L1

Type de L3
***********
'***°*
**********
*****"

condition suffisante mais pas necessaire sur y pour que L1n L3 =

0.
3. Donner une

4.Donner une condition nécessalre mais pas suisante sur y pour que L2 soit inclus dans L3.

nécessalre et sumsante sur p pour que L1 soit inclus dans L3.

5. Donner la condition

ala confiance en soi est le premier secret du succès » Ralph Waldo Emerson
Universlté de Bejala
Faculté des sciences exactes 2 em8
année License
Département d'lnformatique Année 2014/2015
Module:Théorle des Langages
Epreuve de Moyenne Durée
Nom
Prénom:
Groupe

Exercice 1:(7 points)

Soient L1 et L2 deux langages définis comme suit: L1 =
{we{a, b}', J»la = 2k +1 vec k 2 0} et L2 =
(a' bb)"
1. Trouver les grammaires qui génèrent les langages L1 et L2. (Ne donner que les règles de production)
G1:
G2

2. Calculer L2 l a, L2 ! b, L2 |l ab, L2 1 ba
L2 1 a = L2 1 b=

L2 I ab = L2 ba =
 3. Trouver les automates A1 et A2 adéquats qui reconnaissent Li et Ll.

A1
A2

4. Déduire l'automate A
adéquat reconnaissant L1 U L2, puis trouver l'AEF simple lui
correspondant:
A
AEF Simple:

Exercice2 (8 points)

Soient L1 et L2 deux langagestel que

L1 est défini par l'ensemble: {wela, b, c}'", o =a"b°c" avecn +m2ket n, m, k 2 0}

Les instructions de automate qui reconnait L2 sont les suivantes:

1. Z090 Z0a90 5. aq1 a9final 9. aqo alfinal

2. agoaaago 6. Z091b 2042 10. Z04ob Z092

3. agob 1 7. Z092b Z042

8. Z042 209ftnal
4. aq1b 91

1. Trouver l'automate à pile A1 qui reconnalit Ll par etat final. (ne donner que la fonction des transitions)

A1
2.
Trouver les
paramètres de lautomate
ode
l'automat qui reconnait L2 (Ne pas réécrire les instructions de
A1 transition)

3. Les mots e, aab, abb, ab

appartiennent- ils à L2. (justifier votre
réponse)

4. Trouver le langage L2. (sans justification)

L2

Traier "'Automate adéquat qui reconnait L.2 nLl, (Ne donner que la
fonctlon des transitianc
L2 nL1:
Calcul de
 L'Automate de L2n L1:

Exercice 3 :(5 points)

Choisir la (les) bonne(s) réponse(s): (une réponse fausse éliminerait une

réponse juste dans la même question)
1. le type de la règle Aba aCba est
a. Type o b. Type 1 UJ c. Type 2 d. Type3 0
2. Les lan
detype 1 peuvent être reconnus par:

a. AEFs b. AàP
c.ABL d. MTuring
3. Le mot abb
appartient à l'ensemble:
a. (a, b, c)" D b.a,b) c.{b,bal' 0 d. {b, ab)
4. Pour qu'une règle soit de type 2, il est (..qu'elle soit de type 1. (N signifie 'nécessaire', S
signifie 'suffisant)
a. N etS U b. Net pas S c.Set pas N d. Pas N et pas S

5. Chaque langage de type 2 peut être reconnu par

a. AàP déteministe b.AàP c. AàP non déterministe U d. AEF généralisé

6. Un langage de type 1 peut être généré par une grammaire de type

a. Type 0 0 b. Type 1 U C. Type2 U

d.Type3
7. (.w2.W3)"=, R représente la fonction miroir.

b. wf.wf.of 0D C.
.(.wz) U d.(w.o U
a.
wg.2.0
reconnaisse un mot par pile vide, il est nécessaire que:
8. Pour qu'un AàP

a. Onsolt dans un état final b. La plle soit vide C. l ne reste aucun caractère à lire

est un langage de type :

9. Un langage algébrique

a. Type 0 0 b. Type 1 U c. Type 2 U d. Type3

définie de (.. ..dans .) est un homomorphisnne.

10. L'application longueur

a.
a. (X.,E) dans (N, +,0) b. (X,T,t) aans
(N, )| c.
Longueurn'est pas un homomorphisme

de travail, et 1 % d'inné
« Le talent, c'est 99 % ». Gata Kamsky
 eme
Université de Bejaia 2 année License
Faculté des sciences exactes Année 2016/2017
Département d'Informatique Module: Théorie des
Langages
Epreuve de Moyenne Durée

Exercice 1 :(5 points)

Soient L1, L2, L3 L4 et L5 cinq langages réguliers définis comme suit: Ll

, =
{we{a, b}',a"bcm avecn2 0,k
0 etm2 1}, L2 = {a,c}, L3 = L2 OL1, L4 = L1.L3 et L5 = (L2)° nLi

1. Calculer les langages L3, L4 et L5.

2. Trouver lesgrammaires qui génèrent les langages Ll et L2. (Ne donner que les règles de production).
3. Trouver des AEFs simples et déterministes reconnaissant L4 et Ls. (Ne pas donner les
paramètres)
4 Définir les tous les paramètres de l'AEF qui reconnait L3.

Exercice2 : (7 points)

Soient L1, L2 deux langages tel que:

L1est défini par l'ensemble: {we{a, b}', Jwla = lwlb}

Les instructions de l'automate qui reconnait L2 sont les suivantes
1. 2090a Z0a9o 2. aqa aaqo 3. agob 1
4. aq1b 9 1 5. Z091b Z092 6. Zg92bZ092
7. Z092a Z092 8. Zo92C Z092 9. Z092 Z09final

1. Trouver les paramètres de l'automate qui reconnait L2.(Ne pas réécrire les instructions de transition).
2. Les mots abb, aabb, aab, abbca appartiennent- ils à L2. (justifier votre
3
réponse).
Trouver le langage L2 puis une grammaire de type 2 le
générant. (sans justification).
4. Trouver l'Automate adéquat qui reconnait L1 puis celui
qui reconnait L2 n L1 (Ne donner que les fonctions
des transitions).

Exercice 3:(5 points)

Soient G1, G2, deux grammaires tel que
G1 SaA/ aC G2: S aCSd / aCS /a
A aB CaaCC
B Sb Cdcd
Cb Cc CC

1. Déterminer les paramètres de G1. (Ne pas réécrire les règles de production)
2. Donner le type de chaque règle puis déduire le type chaque grammaire.
3. Les mots aacd et aac peuvent ils être générés par la granmaire G2. (Ne justifiez que si le mot appartient)
4. Trouver les langages L1 et L2 générés par les gramimaires Gl et 62. (Sans justification)
 Exercice 4 :(4 points)

Choisir la (les) bonne(s) réponse(s)

1. La règle Ba aBa est incluse dans 'ensemble des règles de:

a. Type O b. Type 1 U c. Type 2 d. Type3 U

2. Les AàP peuvent reconnaitre les langages de type

a.Type o b. Type 1u C. Type 2 U d.Type3 U

3. Le mot « love » appartient à l'ensemble

a.fe, 1,o,v}" U b. {a, L, e, v} U

o,
c.{lo,ve0 d. (ve,L,0}
4. P'élément neutre de la concaténation des langages est

a.e
b.()0 d.
.

5. un AEF simple ne contient pas:

a. Plusieurs étatsfinaux b. des transitions spontanéesU C. plus decinq états

6. Les langages à contexte lié sont des langages de type:

a. Type 0 U b. Type 1 0 C. Type 2 d. Type3

7. (W1.w2.3)"=. . R représente la fonction miroir.

*******")

a.3 . . U b. » .wf.wi
C. ( . 2 d. (2.g)* .wf
8. les opérations commutatives sont

a.L'intersection b. La concaténation C. L'union

« Le talent, c'est 99 % de travail, et 1 % d'inné ». Gata Kamsky

Université de Bejaia
Faculté des sciences exactes
Département d'informatique
Examen de remplacement: ThL (Théorie des Langages)
2me année informatique
Année universitaire 2017/2018

Exercice l:8 points

Soient les langages suivants:
L=
M
{a'b'c'd', j2i 21}.
{a'b, i21, j 2" et n 20. =

K= {a2ib2icn i2n} n EN (N est l'ensemble des entiers naturels)

P
{a'bcid, iz 1 etj 21}
1. Trouver des
grammaires qui génèrent L, M, P et K1.
2. Calculer K7 n L,
PnL, puis trouver des grammaires générant les
langages trouvés.
Exercice 2: 8 points
Soient la fonction p définie comme suit
p: {a, b, c}" A , tel que: p(a) =1, p{b) = 2,p(c) = -2 et p(e) = 0
Soient les langages suivants: r(a.w la}t P(w
L =
{» ¬ {b,c}, p(w) =0}
M {w E {b,c,a}', p(o) =
0}
1. Démontrer que p est un homomorphisme de monoïdes (à vous de déterminer les lois
de composition internes et les ensembles adéquats).
2. Trouver les langages L et M sans utiliser la fonction p.
3. Trouver les grammaires générant L et M.

Exercice 3:4 points

Trouver un automate où une grammaire pour chacun des langages suivants
Ly = {Les entiers naturels divisbles par 3)

L={ab'a', i20,j20}
Lg = {albltia', i2 0, j20}

Bon courage
 Université Abderrahmane Mira deBéjaia
Faculté des Sciences Exactes Département d'informatique
Rattrapage Théorie des Langages, (Licence 2) 2018/2019

(L'usage du téléphone portable est strictement interdit)

Exercice 1:(6 pts)

Soient les grammaires G! et G2 suivantes
GI : S aA/a G2: S aS/ABb

A Sbb aABb ab

le type de chacune des grammaires GI et G2.

1. Déterminer le type de chaque règle, puis
2. Déterminer les langages L(G1) et L(G2).

Exercice 2:(6 pts)

Soient les deux langages suivants l. et M:

I. = {a'bla',i 2j2 0 M= {a'c'bl,i 2 0,j 20}

qui génèrent L et M.
1. Trouver les grammaires
K.
génère le langage
2. Calculer K =Ln M, puis trouver la grammaire qui

Exercice 3:(8 pts)

trois langages réguliers tel-que
Soient L,M et N
naturels multiples de 3}
L =
{ Les entiers
M =
(ba + b')". (hab)*
contient un nombre pair de a} les
N= {w E {a, b}', w qui reconnaissent
cl deterninistes,
automales à élats finis. simples
1. Trouver des
et N.
langages L, M
suivantes :L I x, M i b, N| a. (Avec x e {1,4,7})
dérivées Bon courage
2. Caleuler les
 Corrigé

Département d'informatique
12/02/2018
Module ThL (Théorie des
Langages),(Licence 2)
EMD :
est strictement interdit
L'usage du téléphone portable
Exercice 1: (6 pts)
suivantes:
Soient les grammaires G1, G2, G3
La grammaire Gl:
Lagrammaire G2: | La grammaire G3:
SaSBC/aSC/E S aB/e S aaA1
aB ab A Sbb/E
BCCB/B
aC ac/a BS
1. Déterminer le type de chaque règle, puis le type de chaque grammaire.

Réponse: (1pt) Réponse (1 pt) Réponse :1 pt)

La grammnaire G2: La grammaire G3:
|La grammaire Gl:
S aB S aaA type...3...
SaSBC type...2. type.3...
S asC SE type...3..... A Sbb type ....
type...2......
S 8 type..3.. aB abb type...1... A type........

BC CB3 type...0.... BS type...3....

BC B type...I......
aC > ac type...i...
aC > a
type..l....

Letype de G1 est...0. Le type de G2 est ..0..... Le type de G3 est ...2...

2. Déterminer le langage généré par chaque grammaire.

Réponse:(1 pt)
Lelangage générépar la grammaire G1 est:
L(G1) = {a, ac, e }

Réponse:(1 pt)
Le langage généré par la grammaire G2 est:

L(G2) = {a'b ,i2 1} U{E}

Réponse (1 pt)
Le langage généré par la grammaire G3 est:

L(G3) {(aa) (bb)' ,i 2

= 0) ufe

1 sur 4
Exercice 2:(7 pts)
Soient les langages suivants:
L = {e,a}. M ={a'b2, i2 1,j2 0.
K = {a2b2, ¬ N (N est l'ensemble des entiers naturels)
i2n n

1. Donner LR.
Réponse (0,5pt) :
LR ={e,a

reconnaissant les
2. Trouver les automates à états finis simples et déterministes (AEF)
langages L et M.

L'AEF reconnaissantL (1 pts): L'AEF reconnaissant M(l pts):

- S3

3. Trouver les grammaires qui génèrent L, M et K1.

L La grammaire qui génère M | La grammaire qui génère K1

La grammaire qui génère (0,5 pt):
(0,5 pt): (0,5 pt):

S AB |S aaSbb/aabb
S a/E A aA/a

B bbB/e

2 sur 4
4. Donnerune condition suffisante mais pas nécessaire sur «n» pourque K, nL = D.

Réponse (05 pt): i>1 i=1

5. Calculer M nL,
MnK, MnK.
Réponse (05 pt):
MnL= a}

Réponse (0,5 pt):

MnK = K, = {a2ib, i21}

Réponse (05 pt):

MK =
K =
{a2b2, i 2n n21

6. Donner une expression régulière qui dénote le langage reconnu

par l'AEF suivant:

b
2

Réponse l pt):

a(b'(ba))ba

3 sur 4
Exercice 3 (7 pts): Soient les langages suivants:
Ly={a'b'e, i2j20}. lh ={a-/b'a', iz 0,j 2 0}
1. Trouver les
grammaires qui génèrent chaque langage
Réponse: (2 pts) Réponse (2 pts)
La grammaire qui génère L1: | La grammaire qui génère L:

S aS/aSBc/e S AB

CB Bc |A aAb/e
aB ab BbbBa/e
bB- bb

2. Calculer le langage L = Li n L2, puis trouver la grammaire qui génère le langage L.

Réponse l pt): Le langage L = Lin Lz est

L= LnLz =
{a', i20}
Réponse (l pt): La grammaire qui génère le langage L = Li n Lz est:

SaS/E

3. Trouver la grammaire qui génère le langage L' = L4U L2 en expliquant en 2 lignes la

démarche suivie dans le calcul
Réponse (0,5 pt): La grammaire qui génère le langage L' = Li U Lzest

S $1/$2
- aS1/aS1Bc/E

cB B c

aB ab

bB b b

S2 A'B
AaA'b/E
B' bbB'a/e
Explication (0,5 pt):
obtfenons un mot uppurtenant à L, (à partir de SI) ou un mot
À partir de l'axiomeS, nous
de S2).
appartenant à Lz (à purtir

4 sur 4