Konstrukce minimálního konečného automatu
Definice 2.18. Necht M = (Q,E,ô,q0,F) je D FA. 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, 10.10.2011
Příklad
IB102 Automaty a gramatiky, 10.10.2011
2
Algoritmus pro eliminaci nedosažitelných stavů FA
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 := Si U {g | 3p G Si, a G E : 5(p, a) = g}
4 i := i + 1
5 until Si = Si-i
6 Q7 := S{
7 M' := ^Mq/^o^HQ')
Korektnost: algoritmus je správný a konečný.
IB102 Automaty a gramatiky, 10.10.2011
3
Příklad
IB102 Automaty a gramatiky, 10.10.2011
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, 10.10.2011
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 Ai/= = (Q/=,E,r;, [go]?^y=), 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 g0-
• Koncové stavy jsou právě ty třídy rozkladu Q/=, které obsahují alespoň jeden koncový stav.
Věta 2.37. Necht M = (Q,Y,,ô,qo,F) je DFA bez nedosažitelných stavů s totální přechodovou funkcí. Pak L(M) = L(M/=).
IB102 Automaty a gramatiky, 10.10.2011
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 = • q 4^ Vw e E*.
w
< i : (S(p,w) G F ^=>   5(q,w) G F)
• p =i q právě když p 3 q nelze "rozlišit" žádným slovem délky < i
• p = q právě když p =z q pro každé i £ No- (= = H^o =0
• 1. =o = {(p, g) | p e F gGí1}
2. =,+i = {(p, q)\p=iq A Va G S : 5(p, a) =ť a)}
IB102 Automaty a gramatiky, 10.10.2011
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+1 := {(p, q)\p=iq A Va G S : S(p, a)     S(q, a)}
5 i := i + 1
e    until =2 = =2_i
s^/=:= (Q/=,V,ri, [qo],F/=) Korektnost algoritmu: důkaz vynechán.
IB102 Automaty a gramatiky, 10.10.2011
8
Intuice
IB102 Automaty a gramatiky, 10.10.2011
9
Příklad
M	a	b	Ať	a	6	=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
<- 6	2	—	^ 6	2	N	5	II	II
7	6	1	N		N	6	1	1
IB102 Automaty a gramatiky, 10.10.2011
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	<r- 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, 10.10.2011
11
Kanonický tvar konečných automatů
Motivace
A4i	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	<- IV	III	1	II
V	II	V	v	<- v	1	II	II
IB102 Automaty a gramatiky, 10.10.2011
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, 10.10.2011
13
Rozšírení konečných automatů I Nedeterministické konečné automaty
IB102 Automaty a gramatiky, 10.10.2011
14
Definice 2.42.      Nedeterministický konečný automat (NFA) je
Ai = (Q,E55, 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®\
• ô(q,e) = {q}
Jazyk prijímaný nedeterministickým konečným automatem M. je
L(M) = {w e Ľ* | %0, w) n F ŕ 0}
IB102 Automaty a gramatiky, 10.10. 2011 15
Příklad
IB102 Automaty a gramatiky, 10.10.2011
Ekvivalence DFA a NFA
Věta 2.43. Pro každý NFA M = (Q, S, 5, go? F) existuje ekvivalentní deterministický konečný automat.
Důkaz. Definujeme DFA M! = {Q1E, 5', {g0}, F')
• Qr — 2®\ tj. stavy automatu TW' jsou všechny podmnožiny Q.
• č'(P,a) = \JqeP5{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, 10.10.2011
17
Korektnost
• M.' je deterministický konečný automat.
• Á4 a M1 jsou ekvivalentní:
/\ -—
indukcí k délce w £ S* dokážeme: 5(go,^) = ^({(Zojjw)
^ -— 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) = 5X%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 (/)
IB102 Automaty a gramatiky, 10.10.2011
18
Algoritmus transformace N FA na ekvivalent. D FA
Vstup: Nedeterministický konečný automat M. = (Q,E,S,qo,F). Výstup: Ekvivalentní DFA M' = (Q', E, ô', {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 :=Up€MÓ(Pia)
Q' := Q' U {N} 8 S' := ô'U {((M, a), N)} od
p Done := Done U {M}
20 od
« Ať := (Q',E,<5',{go},F')
IB102 Automaty a gramatiky, 10.10.2011
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, 10.10.2011