Konstrukce minimálního konečného automatu
Definice 2.18. Necht M = (Q, S,ô,q0,F) je konečný automat. Stav q G Q nazveme dosažitelný, pokud existuje w G S* takove, že 5(q0 , w) = q. Stav je nedosažitelný, pokud není dosažitelný.
IB102 Automaty a gramatiky, 11.10.2010
1
Příklad
IB102 Automaty a gramatiky, 11.10.2010
2
Algoritmus pro eliminaci nedosažitelných stavů FA
Vstup:    Konečný automat M = (Q, S, ô, q0, F).
Výstup: Ekvivalentní automat M' bez nedosažitelných stavU.
1 i := 0
2 Si := {qo}
3 repeat Si+1 := Si U {q | 3p G     a G S : ô (p, a) = q}
4 i := i + 1
5 until Si = Si-1
6 Q' := Si
7 M' := (Q', S,ô|q',qo,F n Q') Korektnost: algoritmus je správný a koneCný.
IB102 Automaty a gramatiky, 11.10.2010
3
Příklad
IB102 Automaty a gramatiky, 11. 10. 2010
4
Eliminace ekvivalentních stavů
Necht M = (Q, S,S, q0, F) je FA bez nedosažitelných stavů, jehož přechodová fůnkce je totální.
Definice 2.32. Stavý p, q nazveme jazykové ekvivalentní, psáno p = q, pokůd
p = q Vw G S* : (Š(p,w) G F <5(q, w) G F).
IB102 Aůtomatý a gramatiky, 11.10.2010
5
p = q Vw G S* : (<5(p, w) G F <5(q, w) G F)
Definice 2.34. Reduktem automatu M = (Q, S, 5, q0, F) nazveme konečný automat M/= = (Q/=, S, n, [qo],F/=), kde:
• Stavý jsou trídý rozkladu Q/= (třída obsahující stav q je [q]).
• Prechodova funkce n je funkce splňující:
Vp,q G Q, Va G S: 5 (q,a)= p =^> n ([q],a) = [p].
• Pocatecn í stav je tr ída rozkladu Q/= obsahuj ící stav q0.
• Koncove stavý jsou prave tý tň ídý rozkladu Q/=, které obsahuj í alesponň jeden koncový stav.
Veta 2.37. Necht M = (Q, S, 5, q0, F) je FA bez nedosazitelných stavu s totalní pňechodovou funkc í. Pak L(M) = L(M/=).
IB102 Automatý a gramatiký, 11.10.2010
6
Algoritmus konstrukce minimainího automatu
Definice 2.38. Pro každe i G N0 definujeme binarní relaci =i na Q předpisem
p =i q        Vw G S*.|w| < i : (<5(p, w) G F <^=>   <5(q, w) G F)
• p =i q prave kdýž p a q nelze "rozlišit" zadným slovem delký < i
• p = q prave kdýz p =i q pro kazde i G N0. (= = P|°=0 =i)
• 1. =o = {(p, q) | p G F       q G F}
2. =i+i = {(p, q) | p =i q A Va G S : ô (p, a) =i ô (q, a)}
IB102 Automatý a gramatiký, 11. 10. 2010
7
Algoritmus konstrukce minimálního automatu
Vstup:     Konečný automat M = (Q, S, ô, q0, F) bez nedosažitelných stavu s totainí prechodovou funkcí. Výstup:   Redukt M/=.
1 i := 0
2 =o := {(p, q) | p G F        q G F}
3 repeat
4 =í+1 := {(p, q) | p =i q A Va G S : ô (p, a) =i ô (q, a)}
5 i := i + 1
6 until =i = =i-1
8 M/= := (Q/=, S, n, [qo],F/=) Korektnost algoritmu: dukaz výnechan.
IB102 Automatý a gramatiký, 11. 10. 2010
8
Intuice
IB102 Automaty a gramatiky, 11. 10. 2010
9
Příklad
	M	a	b		M'	a	6	=0	a	b
—>	1	2	—	—	1	2		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	N	1	1
<—	5	6	3	—	5	6	3	II 3	II	II
—	6	2	—	—	6	2		5	II	II
	7	6	1		TV	TV		6	1	1
IB102 Automaty a gramatiky, 11.10.2010
10
Příklad
=1	a	b	=2	a	b
1 1	II	1	1 1	III	II
N	1	1	II N	II	II
II 2	III	II	III 2	IV	III
4	III	II	4	IV	III
III 3	IV	III	IV 3	V	IV
5	IV	III	5	v	IV
IV 6	II	1	V 6	III	II
M/=	a	b
1	III	II
II	II	II
III	IV	III
IV	V	IV
v	III	II
IB102 Automaty a gramatiky, 11.10.2010
11
Kanonický tvar konečných automatů
Motivace
A4i	a	c	b	M2	a	b	c
1	IV	III	1	1	III	V	V
—>	V	III	III	II	IV	II	V
<—	II	1	1	III	1	III	III
<- IV	v	1	II	<- IV	III	1	II
V	II	V	V	^ V	1	II	II
IB102 Automaty a gramatiky, 11.10.2010
12
Kanonický tvar konečných automatů
—> <— <—
	a	c	b
1	IV	III	1
II	V	III	III
III	II	1	1
IV	v	1	II
v	II	V	v
—
	a	b	c
A			
B			
C			
D			
E			
IB102 Automaty a gramatiky, 11. 10. 2010
13
Rozšírení konečných automatů I Nedeterministické konečne automaty
IB102 Automaty a gramatiky, 11.10.2010
14
Definice 2.42.      Nedeterministický konečný automat (NFA) je
M = (Q, S, ô, q0, F), kde význam vsech složek je stejný jako v definici FA s výjimkou prechodove funkce ô. Ta je definovaná jako (totain í) zobrazen í ô : Q x S — 2Q.
RozSírena prechodová funkce ô : Q x S* — 2Q:
• ô(q,wa) = \Jpes(q,w) ô(p,a)
Jazýk prij ímaný nedeterministickým konecným automatem M je
L(M) = {w G S* | ô(qo, w) n F = 0}
IB102 Automatý a gramatiký, 11.10.2010
15
Příklad
IB102 Automaty a gramatiky, 11. 10. 2010
16
Ekvivalence DFA a NFA
Veta 2.43. Pro každy NFA M = (Q, S, ô, q0, F) existuje ekvivalentní deterministicky FA (DFA).
Důkaz. Definujeme deterministicky FA M' = (Q7, S, ô', {q0},F')
• Q' = 2Q, tj. stavy automatu M' jsou všechny podmnožiny Q.
• ô = u qeP ô (q,a).
• Množina koncovych stavu F' je tvorena prave temi podmnožinami Q, ktere obsahují nejaky prvek množiny F.
IB102 Automaty a gramatiky, 11. 10. 2010
17
Korektnost
M' je deterministický konecný automat.
• M a M' jsou ekvivalentn í: indukc í k delce w G S* dokazeme: <5(q0,w) = 5'({q0},w)
Základní krok |w| = 0: Plat í <5(q0, e) = {q0} = 5'({q0}, e). IndukCní krok: Necht w = va, pak
%0,va) = upG(5(q0,v) 5(p,a) = 5'((^(q0,V),a) (viz definice 5')
= 5'(5'({q0},v),a) (indukcn í pňedpoklad) = 5'({q0}, va).
Pak L(M) = L(M'), nebot
w G L(M) <5(q0,w) n F = 0
5'({q0},w) n F = 0 ^ 5'({q0},w) G F' ^ w G L(M'). □
IB102 Automatý a gramatiký, 11. 10. 2010
18
Algoritmus transformace NFA na ekvivalent. DFA
Vstup:   Nedeterministický FA M = (Q, S, ô, q0, F). Výstup: Ekvivalentní deterministický FA M7 = (Q7, S, ô7, {q0}, F7) bez nedosažitelných stavu a s totainí prechodovou funkcí.
1 Q7 := {{qo}};   ô7 := 0;   F7 := 0;    Done := 0;
2 while (Q7 \ Done) = 0 do
3 M := libovolný prvek mnozinýQ7 \ Done
4 if M n F = 0 then F7 := F7 U {M} fi
5 foreach a G S do
6 N := upeM ô(p,a)
7 Q7 := Q7 U {N}
8 ô7 := ô7 U {((M, a), N)} od
9 Done := Done U {M}
10 od
11 M7 := (Q7, S, ô7, {qo},F7)
IB102 Automatý a gramatiký, 11. 10. 2010
19
Důsledky determinizace konečných automatů
Veta 2.44. Pro každé n G N existuje NFA o n stavech takovy, že ekvivalentní DFA ma i po minimalizaci 2n stavu.
Důkaz: vynechan.
IB102 Automaty a gramatiky, 11. 10. 2010
20