Konstrukce minimálního konečného automatu
Definice 2.18. Necht M = (Q,E,ô,q0,F) je DFA. Stav q e nazveme dosažitelný, pokud existuje w £ E* takové, že 5(qo,w) — Stav je nedosažitelný, pokud není dosažitelný.
IB102 Automaty a gramatiky, 8.10. 2012
Příklad
IB102 Automaty a gramatiky, 8.10. 2012
2
Algoritmus pro eliminaci nedosažitelných stavů DFA
Vstup: Deterministický konečný automat Ai = (Q, E, 5, qo, F). Výstup:  Ekvivalentní automat M.' bez nedosažitelných stavů.
1 i := 0
2 Si := {go}
3 repeat S^+i := Si U {g | 3p G     a G S : 5(p, a) = g}
4 i := i + 1
5 until Si =
7M' := ^Mo'xE^o^nQ')
Korektnost: algoritmus je správný a konečný.
IB102 Automaty a gramatiky, 8.10. 2012
3
Příklad
IB102 Automaty a gramatiky, 8.10. 2012
4
Eliminace ekvivalentních stavů
Necht M = (Q, S, 5, qo,F) je DFA 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 £ E* : (Š(p, w) G F Š(q, w) G F).
IB102 Automaty a gramatiky, 8.10. 2012
5
p = q \/w G E* : (S(p, w) G F w) G F)
Definice 2.34. Reduktem automatu Ai = (Q, S, 5, qo,F) nazveme konečný automat M/= = (Q/=,E,r;, [g0],^7=)ř kde:
• Stavy jsou třídy rozkladu Q/= (třída obsahující stav g je [g]).
• Přechodová funkce r] je funkce splňující:
Vp, g G Q, Va G E : 5(q,a)=p =^> r)([q],a) = \p].
• Počáteční stav je třída rozkladu Q/= obsahující stav go-
• Koncové stavy jsou právě ty třídy rozkladu Q/=, které obsahují alespoň jeden koncový stav.
Věta 2.37. Necht M = (Q, S, 5, qo,F) je DFA bez nedosažitelných stavů s totální přechodovou funkcí. Pak L(M) = L(M/=).
IB102 Automaty a gramatiky, 8.10. 2012
6
Algoritmus konstrukce minimálního automatu
Definice 2.38. Pro každé i G No definujeme binární relaci =i na Q předpisem
p =i q <=^ \/w G E*.\w\ < i : (5(p, w) G F <=ŕ   ô(q, w) G 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 G No- (= = Hi^o =*)
• 1. =o = {(p, g) | p G F ?GF}
2. =i+i = {(p,    | p =i g A VaGS:5(p,a)     <S(g, a)}
IB102 Automaty a gramatiky, 8.10. 2012
7
Algoritmus konstrukce minimálního automatu
Vstup:    Deterministický konečný automat M = (Q, S, 5, qo,F)
bez nedosažitelných stavů s totální přechodovou funkcí. Výstup:   Redukt M/=.
ii:=0
2 =o := {(p, q) | p e F        q e F}
3 repeat
4 =i+i := {(p, q)\p=iq A Va G S : ô(p, a) =; ô(q, a)}
5 i := i + 1
e    until =2 = =2_i
s^/=:= (g/=,S,r,, [gô],F/=) Korektnost algoritmu: důkaz vynechán.
IB102 Automaty a gramatiky, 8.10. 2012
8
Intuice
IB102 Automaty a gramatiky, 8.10. 2012
9
Příklad
M	a	b	Ať	a		=0	a	b
1	2	—	->• 1	2	N	1 1	1	1
2	3	4	2	3	4	2	II	1
<- 3	6	5	<- 3	6	5	4	II	1
4	3	2	4	3	2	iV	1	1
<- 5	6	3	<- 5	6	3	II 3	II	II
<r- 6	2	—	<- 6	2	N	5	II	II
7	6	1	N		N	6	1	1
IB102 Automaty a gramatiky, 8.10. 2012
10
Příklad
=1	a	b		= 2	a	b			
1 1	II	1	1	1	III	II	M/=	a	b
N	1	1	II	N	II	II	1	III	II
II 2	III	II	III	2	IV	III	II	II	II
4	III	II		4	IV	III	III	IV	III
III 3	IV	III	IV	3	V	IV	<- IV	V	IV
5	IV	III		5	v	IV	<r- V	III	II
IV 6	II	1	v	6	III	II			
IB102 Automaty a gramatiky, 8.10. 2012
11
Kanonický tvar konečných automatů
Motivace
Mí	a	c	b	M2	a	b	c
1	IV	III	1	1	III	V	V
II	V	III	III	II	IV	II	V
III	II	1	1	III	1	III	III
<r- IV	v	1	II	<r- IV	III	1	II
V	II	V	v	f- V	1	II	II
IB102 Automaty a gramatiky, 8.10. 2012
12
Kanonický tvar konečných automatů
	a	c	b		a	b	c
1	IV	III	1	A			
II	V	III	III	B			
III	II	1	1	C			
<r- IV	v	1	II	D			
V	II	V	v	E			
IB102 Automaty a gramatiky, 8.10. 2012
13
Rozšírení konečných automatů I Nedeterministické konečné automaty
IB102 Automaty a gramatiky, 8.10. 2012
14
Definice 2.42.      Nedeterministický konečný automat (NFA) je
Ai = (Q, E, 5, qo, F), kde význam všech složek je stejný jako v definici DFA s výjimkou přechodové funkce ô. Ta je definována jako (totální) zobrazení á:QxS^ 2Q.
Rozšířená přechodová funkce ô : Q x S* —> 2®\
• S(q,e) = {q}
• 6{q,wa) = Upe5(q,w)ô(P'a)
Jazyk přijímaný nedeterministickým konečným automatem M. je
L(M) = {w e Ľ* | %0, w) n F ŕ 0}
IB102 Automaty a gramatiky, 8.10. 2012 15
Příklad
IB102 Automaty a gramatiky, 8.10. 2012
Ekvivalence DFA a N FA
Věta 2.43. Pro každý N FA M = (Q, S, 5, go? ^) existuje ekvivalentní deterministický konečný automat.
Důkaz. Definujeme DFA M! = (Q', E, {g0},
• Q' — 2®\ tj. stavy automatu yVÍ' jsou všechny podmnožiny Q.
• 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, 8.10. 2012
17
Korektnost
• M1 je deterministický konečný automat.
• Á4 a M* jsou ekvivalentní:
S\ ■------
indukcí k délce w £ S* dokážeme: 5(go,^) = ^'({(ZoIjW)
^ -— Základní krok \w\ = 0: Platí 5(qo,e) = {go} = ^({?o}^)-
Indukční krok: Necht w = va, pak
S(q0,va) = UPeá(go,v)<*(P>a) = 5'(%o^),a) (viz definice 5') = S'(S'({qo}, v), a) (indukční předpoklad) = S'({qo},va).
Pak L(M) = neboí
w e L(M) ô(q0,w) n F ^ ^}
S'({q0},w)nF ŕ 0 <=^t> ^({^o},™) G      ^ weL(M'). □
IB102 Automaty a gramatiky, 8.10. 2012
18
Algoritmus transformace N FA na ekvivalentní D FA
Vstup:   Nedeterministický konečný automat M. = (Q,E,S,qo,F). Výstup: Ekvivalentní DFA M' = (Q'} E, S'} {q0}, F')
bez nedosažitelných stavů a s totální přechodovou funkcí. 2 Q' ;= {{q0}};   ô' := 0;   F' := 0;   Done := 0;
2 while {Q' \ Done) ^ 0 do
3 M := libovolný prvek množiny Q' \ Done
4 if M n F / 0 then F' := F' U {M} fi
5 foreach a G E do
6 N :={JPeMS(P'a) r Q' := Q' U {iV}
s 5' := ô'U {((M, a), N)} od
p Done := Done U {M}
20 od
h M' := (Q', E, <*',{<?()}, F')
IB102 Automaty a gramatiky, 8.10. 2012
19
Důsledky determinizace konečných automatů
Věta 2.44. Pro každé n £ N existuje N FA o n stavech takový, ekvivalentní DFA má i po minimalizaci 2n stavů.
Důkaz: vynechán.
IB102 Automaty a gramatiky, 8.10. 2012