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, gramatiky a složitost, 30.9.2013 Příklad IB102 Automaty, gramatiky a složitost, 30.9.2013 2 Algoritmus pro eliminaci nedosažitelných stavů DFA Vstup: Deterministický konečný automat M = (Q, S, 5, qo,F) Výstup: Ekvivalentní automat M.' bez nedosažitelných stavů. 1 i := 0 2 Si := {q0} 3 repeat Si+i := Si U {q \ 3p £ a £ S : 5(p, a) = g} 4 i := i + 1 5 until Si = ^ Qf \— Si ?M' := Mq'xE, «70,^ h Q') Korektnost: algoritmus je správný a konečný. IB102 Automaty, gramatiky a složitost, 30.9.2013 3 Příklad IB102 Automaty, gramatiky a složitost, 30.9.2013 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, gramatiky a složitost, 30.9.2013 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, gramatiky a složitost, 30.9.2013 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 w < i : (S(p,w) G F S(q,w) G F) • p =1 q právě když p 3 q nelze "rozlišit" žádným slovem délky < i • p = q právě když p =i q pro každé i g No. (= = H^o =0 • 1. =o = {(p, | p g F gef} 2. =i+1 = {(p, q) \p=iq A Va g E : č(p, a) a)} IB102 Automaty, gramatiky a složitost, 30.9.2013 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, gramatiky a složitost, 30.9.2013 8 Intuice IB102 Automaty, gramatiky a složitost, 30.9.2013 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, gramatiky a složitost, 30.9.2013 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