Scribd
Importer
129 vues3 pages

Corrigé TD2 : Automates et Minimisation

Transféré par

OUSSEMA KACHTI
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
129 vues3 pages

Corrigé TD2 : Automates et Minimisation

Transféré par

OUSSEMA KACHTI
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

TD2 Compilation. Corrigé.

Exercice 1.

Algo de Thompson ER  AFN


a
AFN de a n
b n
AFN de b n Ɛ
n

Ɛ b Ɛ
AFN de b* n nn
Ɛ n nn

AFN de ab* a
S1 S2 Ɛ S3 Ɛ S4 b S5 Ɛ S6
n nn
Ɛ n nn

a Ɛ b
AFN de ab n
Ɛ n

S7 Ɛ S8 a S9
Ɛ S10 b S11 Ɛ S12
AFN de (ab)* n
n

AFN de (ab*) | (ab)* Ɛ AFN de ab* Ɛ


S13
S0
Ɛ Ɛ n
les états s1 et s7 ne AFN de (ab)*
n
sont plus initiaux et s6 et s12

ne sont plus finaux.

Déterminisation

Ɛ-fermeture (S0) = q0 = { S0 , S1 , S7 , S8 , S12 , S13 } q0 est un état initial et final.


Δ(q0, a)={ S2 , S9} ; Ɛ-fermeture (S2) = { S2 , S3 , S4 , S6 , S13 } ; Ɛ-fermeture (S9) = { S9 , S10};

Δ(q0, a)= q1 = { S2 , S3 , S4 , S6 , S9 , S10 , S13 } q1 est un état final.

Δ(q0, b)= Ø

Δ(q1, a)= Ø

Δ(q1, b)={ S5 , S11} ; Ɛ-fermeture (S5) = { S4 , S5 , S6 , S13 } ; Ɛ-fermeture (S11) = { S8 , S11 , S12, S13};

Δ(q1, b)= q2 = { S4 , S5 , S6 , S8 , S11 , S12 , S13 } q2 est un état final.

Δ(q2, a)={ S9} ; Ɛ-fermeture (S9) = { S9 , S10} ; Δ(q2, a)= q3 = { S9 , S10} .

Δ(q2, b)={ S5} ; Ɛ-fermeture (S5) = { S4 , S5 , S6 , S13 } ; Δ(q2, b)= q4 = { S4 , S5 , S6 , S13 } q4 est un état final.

Δ(q3, a)= Ø.

Δ(q3, b)={ S11} ; Ɛ-fermeture (S11) = { S8 , S11 , S12 , S13 } ; Δ(q3, b)= q5 = { S8 , S11 , S12 , S13 } q5 est un état
final.

Δ(q4, a)= Ø.

Δ(q4, b)={ S5} ; donc Δ(q4, b)= q4.

Δ(q5, a)={ S9} ; donc Δ(q5, a)= q3.

Δ(q5, b)= Ø.

Le AFD correspondant est donc le suivant :

a b a b
q0 q1 q2 q3 q5
n n n n
n n n b a n

q4
n
n
b
En appliquant l’algorithme de Moore (algo de minimisation), on se rend compte que cet automate
est déjà minimal.

Vous aimerez peut-être aussi