Théorie des langages : Cours automates avec epsilon transitions
Télécharger PDFLes Automates avec EpsilonTransitions1 M. AdilKENZIPlan Automates avec Epsilon-Transitions
Définition
Exemples
Transformation des automates avec epsilon transitions en des automates déterministes Conclusion2 Automates avec Epsilon-Transitions
Definition Un Automate avec epsilon transition ( e-NFA)est donné avec un quintupletA= (Q, S, d, q0 , F) où : Q est l’ensemble d’états, Sest l’alphabet de l’automate, q
0 est l’état initial, F est l’ensemble des états finaux
d: Q S{e}(Q) est la fonction de transition caractérisant une-NFA3 Automates avec Epsilon-Transitions
Exemple 1 :
Un e-NFA qui accepte les nombres décimaux tels que 2.15, .125, +1.4, -0.501...
Pour accepter un nombre tel que “+5.” , on ajoute l’état q4 .4 q5 e
0, 1, ..., 9q 0
e, + , -q 1q 2. 0, 1, ..., 9
0, 1, ..., 9q 3q 4
0, 1, ..., 9. Automates avec Epsilon-Transitions
Exemple2: un autreexempled’un e-NFA définisur
l’alphabet∑ = {a, ..., z}5 SS S2 3e $24 be 96 78 0e bay1 w5 e
Automates avec Epsilon-Transitions
La table de transition complète de l’automate reconnaissant les nombres décimaux6 e+, -. 0, 1, ..., 9q 0q 1q 2q 3q 4q 5{q 1} ff {q5 }f f{q 1} ff ff ff {q2 }
f f{q 3} ff {q1 , q4 }{q 3} {q3 }f f
Transformation d’un e-NFA en un DFA
On définit la fonction e-fermeture et on la note ECLOSE (Epsilonclosureen anglais)définiede Q(Q)comme suit:
1.s ECLOSE (s)
2.Si s1 d(s,e) alors s1 ECLOSE (s)
3.Si s1 ECLOSE(s) Et s2 ECLOSE(s1 ) alorss 2
ECLOSE(s)
On peut définit par extentionECLOSE : (Q )(Q )telle que
ECLOSE(S’ Q) = s ’ S’
e-fermeture(s’) ECLOSE(s) regroupe tous les états accessibles depuis s sur des chemins constitués seulement de e-transitions
Automates avec Epsilon-Transitions
Example ECLOSE(1) ? = {1, 2, 3, 4, 6}
ECLOSE({3, 5}) ? = ECLOSE(3)∪ECLOSE(5) = {3, 6}∪{5, 7} = {3, 5, 6, 7}8 36 ee 17 4e e2 e5 ab Exercice Construire un automate avec e-transitions reconnaissant le langage régulier a* b*c*
Calculer la fonction EClOSEpour chaque état9 Transformation d’un e-NFA en un DFA
Soit AE = <QE , SE , dE , qE0 , FE > un automate non-déterministe avece-transitions (e-NFA), il existe un automate déterministe (DFA) AD = <QD , SD , dD , qD0 , FD > tel que L(A
E )= L(AD )Q D ECLOSE((QE ))
tous les éléments de ECLOSE((SE ))seront accessibles depuis l’état initial de QD S
D = SE dD (sD QD , a SD ) = ECLOSE(s Es Dd E(s E
, a))q D0 = {ECLOSE(qE0 )}F D = {s Q
D | (s FE ) }
Automates avec Epsilon-Transitionsd D
(S, a) est calculée pour chaque symbole ade Set pour chaque Sde QD de cette façon:
soit S= {p1 , p2 , ..., pk }
On calcule d(pi , a) et soit {r1 , r2 , ..., rm } l’ensemble des états résultantd D
(S, a) = ECLOSE( {r1 , r2 , ..., rm }).
Technique pour créeer les états accessibles du DFA D:
on commence de l’état initial q0 du e-NFA E, on crée ECLOSE(q0 ) comme état initial du DFA D qD ;
À partir des états générés , nous dérivons les autres états.11 1k iU Automates avec Epsilon-Transitions
Exemple : eliminationdes e-transitions de l’automateq D
= ECLOSE(q0 ) = {q0 , q1 }d D({q 0
, q1 }, +) = ECLOSE(dE (q0 , +)∪dE (q1 , +)) = ECLOSE({q1 }∪f) = ECLOSE(q1 ) = {q1 }, ...d D({q 0
, q1 }, 0) = ECLOSE(dE (q0 , 0)∪dE (q1 , 0)) = ECLOSE (f∪{q1 , q4 }) = ECLOSE({q1 , q4 }) = {q1 , q4 }, ...d D({q 0
, q1 }, .) = ECLOSE(dE (q0 , .)∪dE (q1 , .)) = {q2 }12 q5 e
0, 1, ..., 9q 0
e, + , -q 1q 2. 0, 1, ..., 9
0, 1, ..., 9q 3q 4
0, 1, ..., 9. Automates avec Epsilon-Transitions
Exemple: 13
+ , -{q 1} {q0 , q1 }{q 1
, q4 }
0, 1, ..., 9{q 2} .
Automates avec Epsilon-Transitions
Exemple: dD ({q1 }, 0) = ECLOSE(dE (q1 , 0)) = ECLOSE({q1 , q4 })
= {q1 , q4 }...d D({q 1
}, .) = ECLOSE(dE (q1 , .)) = ECLOSE({q2 })
= {q2 }14 q5 e
0, 1, ..., 9q 0
e, + , -q 1q 2. 0, 1, ..., 9
0, 1, ..., 9q 3q 4
0, 1, ..., 9. Automates avec Epsilon-Transitions15 + , -{q 1} {q0 , q1 }{q 1
, q4 }
0, 1, ..., 9{q 2} .
0, 1, ..., 9. Automates avec Epsilon-Transitions
Exemple: dD ({q1 , q4 }, 0) = ECLOSE(dE (q1 , 0)∪dE (q4 , 0))
= ECLOSE({q1 , q4 }∪f) = {q1 , q4 }...d D({q 1
, q4 }, .) = ECLOSE(dE (q1 , .)∪dE (q4 , .)) = ECLOSE({q2 }∪{q3 }) = ECLOSE(q2 )∪ECLOSE (q3 )
= {q2 }∪{q3 , q5 } = {q2 , q3 , q5 }16 q5 e
0, 1, ..., 9q 0
e, + , -q 1q 2. 0, 1, ..., 9
0, 1, ..., 9q 3q 4
0, 1, ..., 9. Automates avec Epsilon-Transitions17 0, 1, ..., 9
+ , -{q 1} {q0 , q1 }{q 1
, q4 }
0, 1, ..., 9{q 2} .
0, 1, ..., 9. {q2 , q3 , q5 }. Automates avec Epsilon-Transitions
Exemple: dD ({q2 }, 0) = ECLOSE(dE (q2 , 0)) = ECLOSE({q3 }) = {q3 , q5 } ...d D({q 2
, q3 , q5 }, 0) = ECLOSE(dE (q2 , 0)∪dE (q3 , 0)∪d E(q 5
, 0))=ECLOSE({q3 }∪{q3 }∪f)=ECLOSE(q3 )={q3 , q5 } ...18 q5 e
0, 1, ..., 9q 0
e, + , -q 1q 2. 0, 1, ..., 9
0, 1, ..., 9q 3q 4
0, 1, ..., 9. Automates avec Epsilon-Transitions19 0, 1, ..., 9
+ , -{q 1} {q0 , q1 }{q 1
, q4 }
0, 1, ..., 9{q 2} .
0, 1, ..., 9. {q2 , q3 , q5 }. {q3 , q5 }
0, 1, ...9
0, 1, ...9
Automates avec Epsilon-Transitions
Exemple: dD ({q3 , q5 }, 0) = ECLOSE(dE (q3 , 0)∪dE (q5 , 0)) =ECLOSE({q3 }∪f) =ECLOSE(q3 )={q3 , q5 } ...20 q5 e
0, 1, ..., 9q 0
e, + , -q 1q 2. 0, 1, ..., 9
0, 1, ..., 9q 3q 4
0, 1, ..., 9. Automates avec Epsilon-Transitions21 0, 1, ..., 9
0, 1, ..., 9
+ , -{q 1} {q0 , q1 }{q 1
, q4 }
0, 1, ..., 9{q 2} .
0, 1, ..., 9. {q2 , q3 , q5 }. {q3 , q5 }
0, 1, ...9
0, 1, ...9