Konstrukce minimálního konečného automatu
Definice 2.18. Nechť M = (Q, , , q0, F) je konečný automat.
Stav q  Q nazveme dosažitelný, pokud existuje w  
takové, že
^(q0, w) = q. Stav je nedosažitelný, pokud není dosažitelný.
IB102 Automaty a gramatiky, 6. 10. 2008 1
Příklad
IB102 Automaty a gramatiky, 6. 10. 2008 2
Algoritmus pro eliminaci nedosažitelných stavů FA
Vstup: Konečný automat M = (Q, , , q0, F).
Výstup: Ekvivalentní automat M
bez nedosažitelných stavů.
1 i := 0
2 Si := {q0}
3 repeat Si+1 := Si  {q | p  Si, a   : (p, a) = q}
4 i := i + 1
5 until Si = Si-1
6 Q
:= Si
7 M
:= (Q
, , |Q, q0, F  Q
)
Korektnost: algoritmus je správný a konečný.
IB102 Automaty a gramatiky, 6. 10. 2008 3
Příklad
IB102 Automaty a gramatiky, 6. 10. 2008 4
Eliminace ekvivalentních stavů
Nechť M = (Q, , , q0, F) je FA bez nedosažitelných stavů, jehož
přechodová funkce je totální.
Definice 2.32. Stavy p, q nazveme jazykově ekvivalentní, psáno
p  q, pokud
p  q  w  
: (^(p, w)  F  ^(q, w)  F).
IB102 Automaty a gramatiky, 6. 10. 2008 5
p  q  w  
: (^(p, w)  F  ^(q, w)  F)
Definice 2.34. Reduktem automatu M = (Q, , , q0, F) nazveme
konečný automat M/ = (Q/, , , [q0], F/), kde:
* Stavy jsou třídy rozkladu Q/ (třída obsahující stav q je [q]).
* Přechodová funkce  je funkce splňující:
p, q  Q, a   : (q, a) = p = ([q], a) = [p].
* Počáteční stav je třída rozkladu Q/ obsahující stav q0.
* Koncové stavy jsou právě ty třídy rozkladu Q/, které obsahují
alespoň jeden koncový stav.
Věta 2.37. Nechť M = (Q, , , q0, F) je FA bez nedosažitelných
stavů s totální přechodovou funkcí. Pak L(M) = L(M/).
IB102 Automaty a gramatiky, 6. 10. 2008 6
Algoritmus konstrukce minimálního automatu
Definice 2.38. Pro každé i  N0 definujeme binární relaci i na Q
předpisem
p i q
def
 w  
.|w|  i : (^(p, w)  F  ^(q, w)  F)
* p i q právě když p a q nelze "rozlišit" žádným slovem délky  i
* p  q právě když p i q pro každé i  N0. ( =

i=0 i)
ˇ1. 0 = {(p, q) | p  F  q  F}
2. i+1 = {(p, q) | p i q  a   : (p, a) i (q, a)}
IB102 Automaty a gramatiky, 6. 10. 2008 7
Algoritmus konstrukce minimálního automatu
Vstup: Konečný automat M = (Q, , , q0, F) bez nedosažitelných
stavů s totální přechodovou funkcí.
Výstup: Redukt M/.
1 i := 0
2 0 := {(p, q) | p  F  q  F}
3 repeat
4 i+1 := {(p, q) | p i q  a   : (p, a) i (q, a)}
5 i := i + 1
6 until i = i-1
7  := i
8 M/ := (Q/, , , [q0], F/)
Korektnost algoritmu: důkaz vynechán.
IB102 Automaty a gramatiky, 6. 10. 2008 8
Intuice
IB102 Automaty a gramatiky, 6. 10. 2008 9
Příklad
M a b
 1 2 -
2 3 4
 3 6 5
4 3 2
 5 6 3
 6 2 -
7 6 1
M
a b
 1 2 N
2 3 4
 3 6 5
4 3 2
 5 6 3
 6 2 N
N N N
0 a b
I 1 I I
2 II I
4 II I
N I I
II 3 II II
5 II II
6 I I
IB102 Automaty a gramatiky, 6. 10. 2008 10
Příklad
1 a b
I 1 II I
N I I
II 2 III II
4 III II
III 3 IV III
5 IV III
IV 6 II I
2 a b
I 1 III II
II N II II
III 2 IV III
4 IV III
IV 3 V IV
5 V IV
V 6 III II
M/ a b
 I III II
II II II
III IV III
 IV V IV
 V III II
IB102 Automaty a gramatiky, 6. 10. 2008 11
Kanonický tvar konečných automatů
Motivace
M1 a c b
I IV III I
 II V III III
 III II I I
 IV V I II
V II V V
M2 a b c
 I III V V
II IV II V
III I III III
 IV III I II
 V I II II
IB102 Automaty a gramatiky, 6. 10. 2008 12
Kanonický tvar konečných automatů
a c b
I IV III I
 II V III III
 III II I I
 IV V I II
V II V V
a b c
 A
B
C
D
E
IB102 Automaty a gramatiky, 6. 10. 2008 13
Rozšíření konečných automatů I
Nedeterministické konečné automaty
IB102 Automaty a gramatiky, 6. 10. 2008 14
Definice 2.42. Nedeterministický konečný automat (NFA) je
M = (Q, , , q0, F), kde význam všech složek je stejný jako v definici
FA s výjimkou přechodové funkce . Ta je definována jako (totální)
zobrazení  : Q ×   2Q
.
Rozšířená přechodová funkce ^ : Q × 
 2Q
:
* ^(q, ) = {q}
* ^(q, wa) = p^(q,w) (p, a)
Jazyk přijímaný nedeterministickým konečným automatem M je
L(M) = {w  
| ^(q0, w)  F = }
IB102 Automaty a gramatiky, 6. 10. 2008 15
Příklad
IB102 Automaty a gramatiky, 6. 10. 2008 16
Ekvivalence DFA a NFA
Věta 2.43. Pro každý NFA M = (Q, , , q0, F) existuje ekvivalentní
deterministický FA (DFA).
Důkaz. Definujeme deterministický FA M
= (Q
, , 
, {q0}, F
)
* Q
= 2Q
, tj. stavy automatu M
jsou všechny podmnožiny Q.
* 
(P, a) = qP (q, a).
* Množina koncových stavů F
je tvořena právě těmi podmnožinami Q,
které obsahují nějaký prvek množiny F.
IB102 Automaty a gramatiky, 6. 10. 2008 17
Korektnost
* M
je deterministický konečný automat.
* M a M
jsou ekvivalentní:
indukcí k délce w  
dokážeme: ^(q0, w) = ({q0}, w)
Základní krok |w| = 0: Platí ^(q0, ) = {q0} = ({q0}, ).
Indukční krok: Nechť w = va, pak
^(q0, va) = p^(q0,v) (p, a) = 
(^(q0, v), a) (viz definice 
)
= 
((q0, v), a) (indukční předpoklad) = (q0, va).
Pak L(M) = L(M
), neboť
w  L(M)  ^(q0, w)  F =  
({q0}, w)  F =   ({q0}, w)  F
 w  L(M
). 2
IB102 Automaty a gramatiky, 6. 10. 2008 18
Algoritmus transformace NFA na ekvivalent. DFA
Vstup: Nedeterministický FA M = (Q, , , q0, F).
Výstup: Ekvivalentní deterministický FA M
= (Q
, , 
, {q0}, F
)
bez nedosažitelných stavů a s totální přechodovou funkcí.
1 Q
:= {{q0}}; 
:= ; F
:= ; Done := ;
2 while (Q
Done) =  do
3 M := libovolný prvek množiny Q
Done
4 if M  F =  then F
:= F
 {M} fi
5 foreach a   do
6 N := pM (p, a)
7 Q
:= Q
 {N}
8 
:= 
 {((M, a), N)} od
9 Done := Done  {M}
10 od
11 M
:= (Q
, , 
, {q0}, F
)
IB102 Automaty a gramatiky, 6. 10. 2008 19
Důsledky determinizace konečných automatů
Věta 2.44. Pro každé n  N existuje NFA o n stavech takový, že
ekvivalentní DFA má i po minimalizaci 2n
stavů.
Důkaz: vynechán.
IB102 Automaty a gramatiky, 6. 10. 2008 20