Automate ni non déterministe

Exemple

({a , b }, {1, 2, 3, 4, 5}, δ, {1, 3, 4}, {3, 5}) où δ est dénie par
la table :
a
a b
→ 1 {2} ∅ 3 b
2 ∅ {3, 5} b
→ 3 {3} ∅ a
→ ∅ {4, 5} 1 2 4
4
b a
5 {4} ∅
5 b

Un mot u est accepté s'il existe, à partir d'un état initial q0 ∈ I ,

un chemin étiqueté par u qui aboutit à un état d'acceptation
qf ∈ F .

5
Automate ni non déterministe
Exemple
a

3 b
b
a
1 2 4
b a
5 b

abab

ba

6
Automate ni non déterministe
Exemple
a

3 b
b
a
1 2 4
b a
5 b

abab est accepté : étiquète le chemin 1 2 5 4 5

autres calculs possibles 1 2 5 4 4 (4 ∈/ F ), 1 2 3 3 blocage,
3 3 blocage, 4 blocage
ba n'est pas accepté :
1 blocage, 3 blocage, 4 4 blocage, 4 5 4 (4 ∈/ F )

6
Automate ni non déterministe
Prolongement de la fonction de transition δ en une fonction
de Q × Σ∗ dans P(Q ) :

δ(q , w ) = l'ensemble des états accessibles en partant de q et après

lecture du mot w
w
q δ(q , w )

S on a pour tous mots u , v :

En toute généralité,
δ(q , uv ) = δ(r , v ) v
r ∈δ(q ,u ) u
q

δ(q , u ) δ(q , uv ) 7
Automate ni non déterministe

Le langage reconnu par un AFN A = Σ, Q , δ, I , F est

l'ensemble des mots

( acceptés par A )
L(A) = w ∈ Σ∗ : δ(i , w ) ∩ F 6= ∅
S
i ∈I

8
Automate ni non déterministe
Déterminisation
Exemple. a
b
b 3
a
1 2 ba 4
5 b

10
Automate ni non déterministe
Déterminisation
Exemple. a
b a
b 3
a 3
1 2 ba 4
a b
5 b a
2, 3 a, b
a b b
1, 3, 4 3, 5 a
b a 4
3, 4
4, 5 a
b
b b
10
Automate ni non déterministe
Déterminisation

Si l'AFN A = Σ, Q , δ, I , F reconnaît L alors

l'AFD Adet = Σ, Qdet , δdet , idet , Fdet où :

Qdet = P(Q ) l'ensemble des parties de Q

δdet la fonction de transition deSP(Q ) × Σ → P(Q )
dénie par δdet (X , a ) = δ(q , a )
q ∈X

idet = I
Fdet = {X ⊂ Q : X ∩ F 6= ∅} l'ensemble des parties
comprenant un état d'acceptation
reconnaît également L.
S
w ∈ L(A) ⇔ δ(i, w ) ∩ F 6= ∅ ⇔ δdet (I , w ) ∩ F 6= ∅ ⇔ δdet (I , w ) ∈ Fdet
i∈I
⇔ w ∈ L(Adet )

11
Automate ni non déterministe
Algorithme de déterminisation

Concrètement l'ensemble des états de l'AFD comprend uniquement les

parties accessibles de l'état initial.

On les caractérise via un parcours du graphe de l'AFD qui visite tous les

sommets accessibles à partir de son état initial.

Entrée : l'AFN A = (Σ,Q,δ ,I,F)

Sortie : l'AFD Adet = (Σ,Qdet ,δ ,I,Fdet ) Fdet = { X⊂Qdet : X ∩ F 6= ∅}
Initialisation
Qdet = {I}
VoirSucc = {I}
Traitement
tant que VoirSucc n'est pas vide faire
extraire un élément X de VoirSucc
pour touteSlettre a de Σ
T = δ (q,a)
q ∈ X
δdet (X,a) = T
si T n'est pas dans Qdet alors
ajouter T à Qdet
ajouter T à VoirSucc 12
Automate ni non déterministe
Algorithme de déterminisation
Exemple.
a b a b
→ 1 {2} ∅ → I = {1, 3, 4}
2 ∅ {3, 5}
→ 3 {3} ∅
→ 4 ∅ {4, 5}
5 {4} ∅

a
b
b 3
a
1 2 ba 4
5 b

13
Automate ni non déterministe
Algorithme de déterminisation
Exemple.
a b a b
→ 1 {2} ∅ → I = {1, 3, 4} {2, 3} {4, 5}
2 ∅ {3, 5} {2,3} {3} {3, 5}
→ 3 {3} ∅ {4,5} {4} {4, 5}
→ 4 ∅ {4, 5} {3} {3} ∅
5 {4} ∅ {3,5} {3, 4} ∅
a {4} ∅ {4, 5}
∅ ∅ ∅
{3,4} {3} {4, 5}
b
b 3
a
1 2 ba 4
5 b

13
Automate ni non déterministe
Algorithme de déterminisation

Quel est son coût ?

En O (|Σ| × |Qdet |) : le coût du parcours du graphe de l'AFD qui
a |Qdet | sommets et |Qdet | × |Σ| arcs.
Hors le passage d'un AFN à un AFD peut coûter cher en nombre
d'états.
Dans le pire cas, c'est exponentiel |Qdet | = |P(Q )| = 2|Q | .

Exemple : (a + b)∗ a (a + b)n−1

L'ensemble des mots dont la n-ème lettre en partant de la n est
un a est reconnu par un AFN avec n + 1 mais tout AFD qui le
reconnaît a au moins 2n états.

14
a, b
a a, b a, b
0 1 2 3 l'AFN pour (a + b )∗ a (a + b )2

a
a aaa
b a baa b
a b aab
bbb bba ab a l'AFD
coût de sa construction ∼ 2 3

a aba b
b bab
a b abb
b

15
Automate ni non déterministe avec ε-transitions
Une généralisation des AFN avec des transitions étiquetées avec le
mot vide ε. Lorsque l'automate choisit une telle transition, il ne
consomme pas de lettre.
ε, b d
ε
0 1 2 3
a a c
ε, a 4
ε
5 b
Un mot w est accepté, s'il existe un chemin étiqueté par w d'un
état initial à un état nal.
(chemin de longueur |w |+ le nombre de ε-transitions empruntées)

ac
aaba
abba
16
Automate ni non déterministe avec ε-transitions
Une généralisation des AFN avec des transitions étiquetées avec le
mot vide ε. Lorsque l'automate choisit une telle transition, il ne
consomme pas de lettre.
ε, b d
ε
0 1 2 3
a a c
ε, a 4
ε
5 b
Un mot w est accepté, s'il existe un chemin étiqueté par w d'un
état initial à un état nal.
(chemin de longueur |w |+ le nombre de ε-transitions empruntées)

ac est accepté 0 −→ 1 −→ 2 −→ 3
a ε c

aaba est accepté 0 −→ 1 −→ 0 −→ 1 −→ 0 −→ 4 −→ 5

a ε a b a ε

abba n'est pas accepté

16
Automate ni non déterministe avec ε-transitions

Ajouter des ε-transitions n'augmente pas les capacités de

reconnaissance de l'automate :
Proposition

Tout langage reconnu par un AFN avec ε-transitions l'est aussi par
un AFN sans ε-transitions.
Preuve constructive : il existe un algorithme qui étant donné un
AFN avec ε-transitions construit un AFN sans ε-transitions
équivalent et avec le même nombre d'états.

17
Automate ni non déterministe avec ε-transitions

Grâce aux ε-transitions, on peut toujours se ramener à des

automates (avec ε-transitions) qui ont un unique état initial et un
unique état nal.

ε ε
ε

ε ε

21
Automate ni non déterministe avec ε-transitions
Propriétés de stabilité

ε A1 ε
• Union
ε A2 ε

• Concaténation A1
ε
A2

• Étoile ε
A1
ε

22
État des lieux
Les trois objets introduits :
• AFD,
• AFN,
• AFN avec ε-transitions
ont la même capacité de calcul.
Autrement dit, les classes de langages reconnaissables par AFD,
AFN avec ou sans ε-transitions sont identiques. Tous ces
automates caractérisent l'ensemble des langages réguliers.

De plus, le théorème de Kleene assure l'équivalence entre

expressions régulières et automates nis.

Bilan
AFD, AFN avec ou sans ε-transitions et expressions régulières
dénissent la même classe de langages.
23
D'expression régulière vers automate ni
Une autre variante : l'algorithme de Thompson

Entrée : une expression régulière

(b + ab )∗ (ε + ab )

Étape 1. Construction de l'arbre syntaxique associé à l'expression.

•
∗ +
+ ε •
b • a b
a b

Étape 2. Construction d'un AFN avec ε-transitions via un parcours

en profondeur postxé de l'arbre. Chaque fragment a un seul état
initial, un seul état nal et aucun arc arrivant dans l'état initial ou
partant de l'état nal.
29
 • • •

∗ + ∗ + ∗ +

+ ε • + ε • + ε •

b • a b
b • a b b • a b
a a b
a b b
• •

∗ + ∗ +
b ε •
+ ε • ε ε
ε ε
b a ε b a b a ε b a b

···
30
D'expression régulière vers automate ni
Complexité de l'algorithme de Thompson

b
ε ε ε
ε a ε b ε ε ε
ε ε ε

ε ε ε
a ε b

Coût de l'algorithme de Thompson :

- Construction de l'arbre de syntaxe de taille O (|r |) en O (|r |)
étapes
- Construction de l'AFN via un parcours postxé de l'arbre de
taille O (|r |) en O (|r |) étapes

31