Scribd
Importer
168 vues2 pages

TL TD02

Le document contient plusieurs exercices sur les automates finis déterministes et non déterministes, ainsi que sur les expressions régulières. Les exercices portent sur la construction d'automates reconnaissant des langages donnés et sur la démonstration d'équivalence entre expressions.

Transféré par

NoureddineRmila
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
168 vues2 pages

TL TD02

Le document contient plusieurs exercices sur les automates finis déterministes et non déterministes, ainsi que sur les expressions régulières. Les exercices portent sur la construction d'automates reconnaissant des langages donnés et sur la démonstration d'équivalence entre expressions.

Transféré par

NoureddineRmila
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

Universit de Tunis El Manar 2013--2014

Facult des Sciences de Tunis


Exercice 2 :
---------------- Sur lalphabet X={x,y} construire les automates finis dterministes
Dpartement des Sciences de reconnaissants les langages suivants :
lInformatique
L1= x* L2=x+ L3=x*y* L4=x+y+
L5=x*y+ L6=(xy)* L7=(x*y)* L8=(x+y+)+
T.D. N2 Thorie des Langages (TL)
Automates dtats finis Exercice 3 :
Dterminer les automates finis dterministes reconnaissant les langages
suivants avec X={a,b,c}
L1= {w X * / w contient abc}
Section : LFI2

Exercice 1 L2= {w X * / w contient aabb}


Dfinir informellement les langages accepts par les automates dterministes
suivants :
Exercice 4 :
Dterminer les automates finis dterministes reconnaissant les langages
2 2 3
a suivants avec
a a
b
1 3 1 a a,b L1= {w {a, b, c}* / w contient un nombre de b multiple de 3}
L2= {w {0,....9}* / w est multiple de 3}
b b
a,b
5 a,b 4
4 a,b Indication : w =3k ssi w[ 1 ] + + w[ |w| ] = 3k, k0 et k0
a,b
Exercice 5:
a 1 a Construire un automate fini dterministe qui accepte les mots sur X={a,b}
2 a reconnus par lautomate fini non dterministe suivant :
a
b b
b 3 4 2
1 b a,b
a,b
b a a
4 b 3

b
b b 5
1 6
b
a
a
2 a

a 4
3
b
Exercice 6 :
Soit M lautomate fini non dterministe suivant : ({q0, q1 ,q2},{a,b},
, q0 ,{ q0 , q2 }) avec :
(q0,a)={ q1, q2 }, (q1,a)={ q0, q1 }, (q2 ,a)={ q2 , q0 }, (q0 ,b)={ q0},

(q2 ,b)={ q1}, (q1 ,b)=

Trouver un automate fini dterministe M acceptant L(M).

Exercice 7 :
Soit lexpression rgulire (a+b)*abb sur lalphabet X={a,b}.
Construire un automate fini non dterministe qui reconnat L((a+b)*abb).
Rendre dterministe lautomate prcdent. Est-il optimal ? si non
loptimiser.

Exercice 8 :

Dmontrer lquivalence des deux expressions


E1 = (b*(a+b)*)* et E2 = (a*b)*

Exercice 9 :
Construire un automate fini dterministe reconnaissant le langage L :

L={ w {a,b,c}* / |w|a=2p+1 et |w|b=2k+1 et |w|c=2n, p,k,n0}

Vous aimerez peut-être aussi