Exercices
Exercice 1. Construire un automate fin déterministe minimal qui accepte
l’ensemble des mots sur le vocabulaire {a,b} contenant un nombre pair de a et
un nombre pair de b.
Considérons L1 le langage contenant un nombre pair de a et L2 le langage
contenant un nombre pair de b.
Nous pouvons construire un automate qui accepte L1 et un automate qui
accepte L2. Ensuite un automate pour le complément de L1 et Un automate
pour le complément de L2 ensuite un automate pour l’union des compléments
ensuite pour le complément de l’union.
Leila Jemni Ben Ayed Théorie des Langages 1
Exercices
b a a
b
a b
A1 q01 q1 A2 q02 q2
a b
a
Pour les compléments nous obtenons:
b a a
b
a b
A1’ q01 q1 A2’ q02 q2
a b
Leila Jemni Ben Ayed Théorie des Langages 2
Exercices
b a a
b
a b
A1’ q01 q1 A2’ q02 q2
a b
Pour l’union des compléments, nous obtenons:
b b
a
q0 q1
A a
b
a
qi
a a
a
b
b q2 q3
b
Leila Jemni Ben Ayed Théorie des Langages 3
Exercices
Rendre déterministe donne, pour l’union des compléments :
a
a b
{qi} A {q1, q2} B {q0, q3} D B a C
a
b
{q1, q2} B {q0, q2} C {q1, q3} E A b E
b a
{q0, q2} C {q1, q2} B {q0, q3} D
a
D
{q0, q3} D { q1, q3} E {q0, q2} C
b b
{q1, q3} E {q0, q3} D {q1, q2} B
Leila Jemni Ben Ayed Théorie des Langages 4
Exercices
La minimisation donne pour l’union des compléments:
a
a
B a C
a
b a B
A b E A
b a b
a b b
D b
b b a
E
Π0 (A, C) (B, D, E) D a
Π1 (A, C) (B) (D) (E)
Π2 (A, C) (B) (D) (E)
A
Leila Jemni Ben Ayed Théorie des Langages 5
Exercices
Le complément de l’union donne l’automate fini déterministe minimal suivant:
a B
A
b
b b b
a
E
D a
Leila Jemni Ben Ayed Théorie des Langages 6
Exercices
Automates finis
Exercice 2.
1) Construire des automates finis déterministes reconnaissant les langages
suivants :
X = {a, b, c}
L1 = {w ∈ X* / w contient un facteur abc}
L2 = {w ∈ X* / w se termine par aabb}
X = {0, 1}
L3 = {w ∈ X* / n(w) = 3k + 1, k ≥ 0} avec w est la représentation binaire de n(w)
L4 = l’ensemble des mots tels qu’il y ait soit deux 0 soit deux 1 consécutifs
2) En déduire des expressions régulières pour chacun des langages L1, L2, L3
et L4.
Leila Jemni Ben Ayed Théorie des Langages 7
Exercices
Automates finis
Exercice 3.
1) Rendre déterministe et minimal l’automate suivant :
M = ({q, r, s}, {a, b}, {(q, b, q), (q, a, r), (q, a, s), (r, a, q), (r, a, r), (s, a, s), (s, a, q),
(s, b, r)}, q, {s})
Minimiser l’automate suivant :
2) M1 = ({1, 2, 3, 4, 5}, {a, b}, 1, {4}, {(1, a, 2), (2, a, 3), (3, b, 4), (4, a, 5), (5, b,
4)})
Leila Jemni Ben Ayed Théorie des Langages 8
Exercices
Corrigé Exercice 2:
A1 / L1 = L(A1)
b, c a a, b, c
a b c
q0 q1 q2 q3
c a
Leila Jemni Ben Ayed Théorie des Langages 9
Exercices
A2 / L2 = L(A2)
b, c a
a a b b
q0 q1 q2 q3 q3
b, c a
c
a
c
b, c
Leila Jemni Ben Ayed Théorie des Langages 10
Exercices
A3 / L3 = L(A3) A4 / L4 = L(A4)
0, 1
0 1
1 0 0
3k 3k+1 q0 q1 q2
0 1
0
0 1
q3 q4
1
3k+2
1
0, 1
Leila Jemni Ben Ayed Théorie des Langages 11
Exercices
2)
L1 : (a+b+c)*abc(a+b+c)*
L2 : (a+b+c)*aabb
L3 : 0*1(10*1)*(01*0)*
L4 : (0+1)*11(0+1)* + (0+1)*00(a+1)*
Leila Jemni Ben Ayed Théorie des Langages 12
Exercices
Corrigé Exercice 3:
1) M = ({q, r, s}, {a, b}, q, {s}, {(q, b, q), (q, a, r), (q, a, s), (r, a, q), (r, a, r), (s, a,
s), (s, a, q), (s, b, r)})
b a b
a
a {q} {r, s} {q}
q r
{r, s} {q, r, s} {r}
a
b
a {q, r, s} {q, r, s} {q,r}
s
{r} { q, r} φ
a a
{q, r} {q, r, s} {q}
Leila Jemni Ben Ayed Théorie des Langages 13
Exercices
1) M = ({q, r, s}, {a, b}, q, {s}, {(q, b, q), (q, a, r), (q, a, s), (r, a, q), (r, a, r), (s, a,
s), (s, a, q), (s, b, r)})
a
b
A b
C
b {q} A {r, s} B {q} A
a a
A {r, s} B {q, r, s} C {r} D
a B
b {q, r, s} C {q, r, s} C {q,r} E
a, b
E {r} D { q, r} E φ
a b
D b B {q, r} E {q, r, s} C {q} A
Leila Jemni Ben Ayed Théorie des Langages 14
Exercices
1) M = ({q, r, s}, {a, b}, q, {s}, {(q, b, q), (q, a, r), (q, a, s), (r, a, q), (r, a, r), (s, a,
s), (s, a, q), (s, b, r)})
a
b
Π0 = (A, D, E, P) (C, B)
C a
b Π1 = (A, E) (D, P) (C, B)
Π2 = (A, E) (D) (P) (C) (B)
a a C
A b b
a B L’automate
b a a
Déterministe
a, b A
E Minimal a, b
B
b a a
a
D b P P
D b b
Leila Jemni Ben Ayed Théorie des Langages 15
Exercices
Minimiser l’automate suivant :
2) M1 = ({1, 2, 3, 4, 5}, {a, b}, 1, {4}, {(1, a, 2), (2, a, 3), (3, b, 4), (4, a, 5), (5, b,
4)})
a a b
1 2 3 4 a
b
a b 5
b b
a
P
a, b
Leila Jemni Ben Ayed Théorie des Langages
Exercices
a a b
1 2 3 4 a
b
a b 5
b b
a
P
G1 G2
Π0 : (1, 2, 3, 5, P) (4) a, b
G1 G2 G3
Π1 : (1, 2, P) (3, 5) (4) a a
1 2 3
G1 G2 G3 G4 b
Π2 : (1,P) (2) (3, 5) (4)
L’automate a
Π3 : (1) (P) (2) (3, 5) (4) Minimal 4
Π4 : (1) (P) (2) (3, 5) (4)
Leila Jemni Ben Ayed Théorie des Langages
