Univérsité de la Manouba
Ecole supérieur de commerce
TD N°3 : Théories des Langages
Exercice 1 :
1
2
Exercice 2 :
3
Grammaire régulière à gauche de A
Grammaire régulière à gauche de B
4
Exercice 3 :
a b
{1} A {2,3} B {4} C
{2,3} B {∅} {4 ,3} D
{4} C {∅} {∅}
{4, 3} D {∅} {4 ,3} D
b
b
B D
a
b
C
Exercice 4 :
a b b
1. 2 3
0 1
a, b
2.
a b
{0} A {0, 1} B {0} A
{0, 1} B {0, 1} B {0,2}C
{0, 2}C {0, 1} B {0,3}D
{0, 3}D {0, 1} B {0} A
a
B
a a
a
b A C
b b
D
5
Exercice 5 :
1. M1 et M2 sont 2 AEFD car ne comprend pas ni epsilon transition ni 2 transitions avec
le même non terminaux à partir du même état
2. M1 =(Q, q0, Transition, Vt, F)
Q0 = 0 ; F ={1} ; Q ={0, 1, 2} ; Vt ={a, b}
Transition : {(0, a) 1; (0, b) 2 ; (1, a) 1 ; (1, b) 1 ; (2, a) 2;
(2, b) 1 }
NB : De même pour M2
3. Pour M1
L0 = aL1 | bL2
L1 = ( a | b) L1 | eps
L2 = a L2 | b L1
D’après le théorème d’ARDEN
L1 = (a | b) L1 | eps
L1= (a | b )*
On replace dans L2
L2 = aL2 | bL1
L2 = aL2 | b(a|b)*
L2 = a*b(a|b)*
On replace dans L0
L0 = aL1 | bL2
L0 = a (a | b )* | b a*b(a|b)* exp reg
Pour M2:
L3 = aL3 | b L4
L4 = aL4 | bL5
L5 =(a |b)L5 | eps
D’après le théorème d’ARDEN
L5 =(a |b)L5 | eps
L5 = (a|b)*
On remplace dans L4
L4 = aL4 | bL5
L4 = aL4 |b(a|b)*
L4 = a*b(a|b)*
6
On remplace dans L3
L3 =aL3 | bL4
L3 = aL3 | b a*b(a|b)*
L3 = a* b a*b(a|b)*
Exercice 6 :
L0 = bL1 | eps
L1 = (a|b) L1 | aL0
D’après le théorème d’ARDEN
L1 = (a|b) L1 | aL0
L1 = (a|b)* aL0
On remplace dans L0
L0 = bL1 | eps
L0 = b (a|b)* aL0 | eps
L0 = (b (a|b)* a)*
