Scribd
Importer
612 vues5 pages

Correction DS Mars 2014

Le document décrit un devoir surveillé sur la théorie des langages et techniques de compilation contenant trois exercices. L'exercice 1 demande de donner une expression régulière et de construire des automates à états finis pour reconnaître un langage binaire. L'exercice 2 porte sur la construction d'automates déterministes. L'exercice 3 demande de construire directement un automate déterministe et de donner des expressions régulières.

Transféré par

inesslimane4
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
612 vues5 pages

Correction DS Mars 2014

Le document décrit un devoir surveillé sur la théorie des langages et techniques de compilation contenant trois exercices. L'exercice 1 demande de donner une expression régulière et de construire des automates à états finis pour reconnaître un langage binaire. L'exercice 2 porte sur la construction d'automates déterministes. L'exercice 3 demande de construire directement un automate déterministe et de donner des expressions régulières.

Transféré par

inesslimane4
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

DEVOIR SURVEILLE

Semestre : 1 2

Session : Principale Rattrapage

Module : Théorie des langages et techniques de compilation


Classes :3A1-10, 4INFOB
Documents autorisés : OUI NON Nombre de pages : 2
Date : 14/03/2014 Heure : 11H00 Durée : 1H00

Exercice 1 : (7 pts)

Soit le langage L des mots construits sur l’alphabet ∑ = {0,1}. Le langage L est constitué par
l’ensemble des séquences de bits de taille strictement supérieure à 1 tel que le premier bit et le
dernier soient identiques.

a) Donner une expression régulière pour le langage L. (2 pts)

REPONSE
1(O|1)*1 | 0(O|1)*0

b) Construire un automate à états fini non déterministe (sans ε-transition) qui reconnaisse
le langage L. (2 pts)
REPONSE

1
c) Rendre cet automate déterministe. (3 pts)

REPONSE

état 0 1
e0 A e2 C e1 B
e1 B e1 B {e1, e3} D
e2 C {e2, e3} E e2 C
{e1, e3} D e1 B {e1, e3} D
{e2, e3} E {e2, e3} E e2 C

2
xercice 2 (3 pts)

On se place sur l’alphabet ∑= {a,b}.

a) Donner l’expression régulière relative à l’automate ci-dessus. (2 pts)

REPONSE
a*(a|b)b*

b) Construire l’automate déterministe correspondant (2 pts).

REPONSE
ε-fermeture (1) = {1, 2, 4, 5, 7} = A
δ (A, a) = {3, 6}
ε-fermeture ({3, 6}) = {2, 3, 4, 5, 6, 7, 9, 10, 12} = B
δ (A, b) = {8}
ε-fermeture (8) = {8, 9, 10, 12} = C
δ (B, a) = {3, 6}
ε-fermeture ({3, 6}) = {2, 3, 4, 5, 6, 7, 9, 10, 12} = B
δ (B, b) = {8, 11}
ε-fermeture ({8, 11}) = {8, 9, 10, 11, 12} = D
δ (C, a) = ∅
δ (C, b) = {11}
ε-fermeture (11) = {10, 11, 12} = E
δ (D, a) = ∅
δ (D, b) = {11}
ε-fermeture ({11}) = {10, 11, 12} = E
δ (E, a) = ∅

3
δ (E, b) = {11}
ε-fermeture (11) = {10, 11, 12} = E
a b
A B C
B B D
C _ E
D _ D
E _ E

c) Donner l’automate minimal équivalent (3 pts)


REPONSE
A BCDE
A B CDE

4
Exercice 3 : (6 pts)

1) Considérons le langage suivant L = {w ∈{a,b}* | w commence par la sous chaine aa


ou bb et contient un nombre impair de a}, Construire directement un automate à états
fini déterministe qui reconnait le langage L. (2 pts)
REPONSE
(aa|bb) (ab*a|b)*ab*

2) On considère l’alphabet ∑ = {a, b}, donner une expression régulière décrivant :


a) Le langage de tous les mots construits sur ∑ qui contiennent au plus deux b et se
terminant par aa. (2 pts)
REPONSE
(a* | (a*b |a*ba*b) a*)aa

b) Le langage L={anbp} avec n et p entiers et l’un des deux est pair (2 pts).
REPONSE
(aa)**(bb)*b | (aa)**a(bb)*

Bon Travail

Vous aimerez peut-être aussi