Scribd
Importer
736 vues6 pages

Correction DS Mars 2014

Le document décrit un devoir surveillé sur la théorie des langages et techniques de compilation. Il contient trois exercices portant sur les expressions régulières, les automates à états finis déterministes et non déterministes, et la reconnaissance de langages formels.

Transféré par

moslem.haddadi
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
736 vues6 pages

Correction DS Mars 2014

Le document décrit un devoir surveillé sur la théorie des langages et techniques de compilation. Il contient trois exercices portant sur les expressions régulières, les automates à états finis déterministes et non déterministes, et la reconnaissance de langages formels.

Transféré par

moslem.haddadi
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