Konstrukce minimálního konečného automatu Definice 2.18. Necht M = (Q, S, 5, go? F) je konečný automat. Stav g G Q nazveme dosažitelný, pokud existuje w G S* takové, že 5( Vw G S* : (S(p,w) G F <=> ö(q,w) G F). IB102 Automaty a gramatiky, 19.10.2009 p = q <=> Vw; G S* : (S(p, w) G F <=> S(q, w) G F) Definice 2.34. Reduktem automatu M, — (Q,£,5, go?^) nazveme konečný automat M/= = (Q/=,£,77, [qo],F/=), kde: • Stavy jsou třídy rozkladu Q/= (třída obsahující stav g je [q]). • Přechodová funkce r/ je funkce splňující: Vp,g £ Q,Va £ S : ô(q,a)=p =^> r/([g],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. Necht M = (Q, S, 5, qo,F) je FA bez nedosažitelných stavů s totální přechodovou funkcí. Pak L (M) = L(A4/=). IB102 Automaty a gramatiky, 19.10.2009 6 55 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 4^ \/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- (= = H^o —0 1- =o = {(p, g) | p G F ^^ g G F} 2. =í+1 = {(p, g) | p =i q A \fa e^ : 5(p, a) =; 5(g, a)} IB102 Automaty a gramatiky, 19.10.2009 7 Algoritmus konstrukce minimálního automatu Vstup: Konečný automat M = (Q, S, 5, go, F) bez nedosažitelných stavů s totální přechodovou funkcí. Výstup: Redukt M/=. i i :=0 2 =o := {(p, g) | p G F ^^ q G F} 3 repeat 4 =í+1 := {(p, g) | p =i q A Va G S : 5(p, a) =i 5{q, a)} 5 i := i + 1 6 until =^ = =^_i «A^=:= (Q/k, 2,^0],^/=) Korektnost algoritmu: důkaz vynechán. IB102 Automaty a gramatiky, 19.10.2009 8 Intuice IB102 Automaty a gramatiky, 19.10.2009 9 M a b 1 2 — 2 3 4 3 6 5 4 3 2 5 6 3 6 2 — 7 6 1 Příklad M' a b 1 2 N 2 3 4 3 6 5 4 3 2 5 6 3 6 2 TV TV TV TV =0 a b 1 1 1 2 II 1 4 II 1 TV 1 1 3 II II 5 II II 6 1 1 IB102 Automaty a gramatiky, 19.10.2009 10 =1 a b 1 II 1 TV 1 1 2 III II 4 III II 3 IV III 5 IV III 6 II 1 Príklad =2 a b 1 III II TV II II 2 IV III 4 IV III 3 V IV 5 V IV 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, 19.10.2009 11 Kanonický tvar konečných automatů Motivace M! a c b 1 IV III 1 II V III III III II 1 1 IV V 1 II V II V V M2 a b c 1 III V V II IV II V III 1 III III IV III 1 II V 1 II II IB102 Automaty a gramatiky, 19.10.2009 12 Kanonický tvar konečných automatů a b c A B C D E a c b 1 IV III 1 II V III III III II 1 1 IV V 1 II V II V v IB102 Automaty a gramatiky, 19.10.2009 13 Rozšírení konečných automatů I Nedeterministické konečné automaty IB102 Automaty a gramatiky, 19.10.2009 14 Definice 2.42. Nedeterministický konečný automat (NFA) je A4 = (Q, £, 5, go? ^)> kde význam všech složek je stejný jako v definici FA s výjimkou přechodové funkce 5. Ta je definována jako (totální) zobrazení í:QxS^ 2Q. Rozšířená přechodová funkce S : Q x S* —> 2^: • <5(?,e) = {í} Jazyk prijímaný nedeterministickým konečným automatem A4 je L(M) = {w e £* | %o, w) n F ^ 0} IB102 Automaty a gramatiky, 19.10. 2009 15 Příklad IB102 Automaty a gramatiky, 19.10.2009 16 Ekvivalence DFA a NFA Věta 2.43. Pro každý NFA M = (Q, S, 5, g0? F) existuje ekvivalentní deterministický FA (DFA). Důkaz. Definujeme deterministický FA Mf = (Q7, S,č7, {go},^7) • Q' = 2®, tj. stavy automatu .M7 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, 19.10.2009 17 Korektnost • Á4f je deterministický konečný automat. • A4 a A4' jsou ekvivalentní: indukcí k délce w £ S* dokážeme: ö(qo,w) = ^'({go}?^) Základní krok \w\ = 0: Platí <5(g0,£) = {qo} = ^'({(Zo}?^)- Indukční krok: Necht w = va, pak S(q0,va) = UpG^o^)5^'0) = ^(%o,^),a) (viz definice 5') = ^(^({go}?^)?^) (indukční předpoklad) = o'({qo},vá). Pzk L(M) = L(M'), neboř w G L(.M) ^^ <5(go,w)nF^0 ^^ ^({gol^ínF^ 0 ^^ £'({go},w) eF' ^^ weL(M'). d IB102 Automaty a gramatiky, 19.10.2009 18 Algoritmus transformace N FA na ekvivalent. DFA Vstup: Nedeterministický FA M = (Q, E, 5, g0? F)-Výstup: Ekvivalentní deterministický FA M' = (Q7, S, č7, {go}? í7") bez nedosažitelných stavů a s totální přechodovou funkcí. ! Q' := {{go}}; £' := 0; F' := 0; Done := 0; 2 while (Q' \ Done) ^ 0 do 3 M := libovolný prvek množiny Q7 \ Done 4 if M n F ^ 0 then F' := F' U {M} fi 5 foreach a G S do 6 N :=\JpeMô(p,a) Q' := Q7 U {N} 8 ôf := (T U {((M, a), AT)} od p Done := Done U {M} io od n AT := (Q', £,<$', {go}, F') IB102 Automaty a gramatiky, 19.10.2009 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, 19.10.2009