chapitre 4
Déterminisation avec -transition
Automate avec -transition
Un automate fini avec -transition est un
automate qui autorise des transitions
étiquetées par le mot vide, qui sont
appelées les transitions spontanées.
chapitre 4
Définition
Un -AFN (non-déterministe) est défini par
un quintuplé T = (A, Q, I, F, μ) où :
– A est un ensemble fini de symboles .
– Q est un ensemble fini d’états.
– I Q est l’ensemble des états initiaux.
– F Q est l’ensemble des états finaux.
– μ est une fonction de transition :
μ : Q× A{} Q
chapitre 4
Exemple
a b c
0 1 2
a b
1 3
a c
2
chapitre 4
Définition
L'ε-fermeture d'un état e ∈ Q d'un AFN
T=(A, Q, I, F, μ), notée ε-fermeture(e),
est l'ensemble des états de T
accessibles depuis l'état e par 0, 1... n
ε-transitions seulement.
chapitre 4
L'ε-fermeture d'un ensemble d'états E ⊂
Q d'un AFN T=(A, Q, I, F, μ), notée ε-
fermeture(E), est l'ensemble des états de
T accessibles depuis chacun des états e
∈ E par des ε-transitions seulement.
ε-fermeture(E)=E ∪ {∪ ε-fermeture(qj) /
∃ qi ∈ E, μ(qi, ε)=qj
chapitre 4
Exemple
a
2 3
0 1 6 7
a
b
4 5
8
chapitre 4
Calculons ε-fermeture(6)
μ(6, ε) = 1 et μ(6, ε) = 7
ε-fermeture(6) = {6} ∪ ε-fermeture(1) ∪
ε-fermeture(7)
μ(1, ε) = 2 et μ(1, ε) = 4
ε-fermeture(1) = {1} ∪ ε-fermeture(2) ∪
ε-fermeture(4)
chapitre 4
μ(2, ε) = ∅ donc ε-fermeture(2) = {2}
μ(4, ε) = ∅ donc ε-fermeture(4) = {4}
ε-fermeture(1) = {1, 2, 4}
μ(7, ε) = ∅ donc ε-fermeture(7)={7}
ε-fermeture(6) = {1, 2, 4, 6, 7}
Définition chapitre 4
La fonction M(E, a) est l'ensemble des
états E' de T vers lesquels il existe une
transition sur le symbole d'entrée a à
partir des états e ∈ E.
Μ(E, a) = {qi} ⊆ Q tels que ∃ μ(p, a) = qi
avec a ∈ A et p ∈ E.
Μ({2,7}, a) = {3,8}.
chapitre 4
Algorithme de
déterminisation
Calcul de T’ = (A, Q′, μ′, I’, F′)
1) I' = ε-fermeture(I) ; Ajouter I' dans Q' ;
2)Pour chaque "état" E (ensemble d'états de T)
non-marqué dans Q' :
a. Le marquer.
b. Déterminer pour chaque symbole a de A
E' = Μ(E, a)
E'' = ε-fermeture(E')
Si E'' n'existe pas dans Q' alors :
• L'ajouter dans Q‘.
• S'il contient un état final de T alors
l'ajouter dans F‘.
Créer une transition μ'(E, a)
chapitre 4
Exemple 1
a
2 a
1 4
a
3
b
chapitre 4
ε-fermeture(E)=E ∪ {∪ ε-fermeture(q j) / ∃
qi ∈ E, μ(qi, ε)=qj
(1, ) = 2 et (1, ) = 3
I' = ε-fermeture(I) = ε-f(1)
= 1 ε-f(2) ε-f(3)
ε-f(2) = 2 et ε-f(3) = 3
I' = {1, 2, 3}
chapitre 4
E’ = Μ(E, a) = M({1, 2, 3}, a) = {2, 4}
E’’ = ε-f({2, 4}) = {2, 4}
E’ = M({1, 2, 3}, b) = {3}
E’’ = ε-f({3}) = {3}
E’ = M({2, 4}, a) = {2, 4}
E’’ = ε-f({2, 4}) = {2, 4}
a b
{1, 2, 3} {2, 4} {3}
{2, 4} {2, 4}
chapitre 4
E’ = M({2, 4}, b) = Ø E’ = M({4}, a) = Ø
E’’ = ε-f(Ø) = Ø
E’’ = ε-f(Ø) = Ø
E’ = M({3}, a) = {4}
E’ = M({4}, b) = Ø
E’’ = ε-f(4) = {4}
E’’ = ε-f(Ø) = Ø
E’ = M({3}, b) = {3}
E’’ = ε-f(3) = {3}
a b
{1, 2, 3} {2, 4} {3}
*{2, 4} {2, 4} Ø
{3} {4} {3}
*{4} Ø Ø
chapitre 4
Exemple 2
0
a a
b
1 2 3
4
chapitre 4
μ a b
{0} = A = I' {1,2,4} ∅
{1,2,4} = B ∈ F’ {3,2,4} {3,2,4}
{2,3,4} = C ∈ F’ {3,2,4} {3,2,4}
a
a
A B C a, b
b
