Rozšírení konečných automatů I Nedeterministické konečné automaty IB102 Automaty, gramatiky a složitost, 7.10.2013 1 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, gramatiky a složitost, 7.10. 2013 2 Příklad IB102 Automaty, gramatiky a složitost, 7.10.2013 3 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, gramatiky a složitost, 7.10.2013 4 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, gramatiky a složitost, 7.10.2013 5 Algoritmus transformace N FA na ekvivalentní DFA 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 W := \}p&M5(p,a) 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, gramatiky a složitost, 7.10.2013 6 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, gramatiky a složitost, 7.10.2013 Rozšírení konečných automatů II Automaty s e-kroky IB102 Automaty, gramatiky a složitost, 7.10.2013 8 Definice 2.46. Nedeterministický konečný automat s e-kroky je Ai = (Q,Yi,ô,qo, F), kde význam všech složek je stejný jako v definici NFA s výjimkou přechodové funkce ô. Ta je definována jako totální zobrazení á:Qx(SU {e}) -> 2Q. Rozšírená přechodová funkce Definujeme funkci D£ : Q 2® následujícím předpisem. D£(p) je nejmenší množina X C Q taková, že platí: • p £ X, • pokud q £ X a r G ô(q,e), pak také r G X. Rozšírení funkce D£ na množiny stavů: pro Y C Q položíme DsiX) = y De(q). qeY IB102 Automaty, gramatiky a složitost, 7.10.2013 9 Příklad - výpočet D IB102 Automaty, gramatiky a složitost, 7.10.2013 10 Definice rozšířené přechodové funkce 5 : Q x S* —> 2® • 5(q,e) = De(q), • Š(q,wa) = \Jp&s(q)W)De(6(p,a)). Lemma 2.47. V přechodovém grafu automatu M. existuje cesta Pi —> ... A pm —> qi —> ... —> qn, kde m, n > 1, a £ E, právě když ?n G 5(pi,a). Jazyk přijímaný automatem M. s e-kroky je L(M) = {w G S* | %0, n F ^ 0} IB102 Automaty, gramatiky a složitost, 7.10. 2013 11 Příklad - výpočet rozšířené přechodové funkce pro automat s e-kroky IB102 Automaty, gramatiky a složitost, 7.10.2013 12 Ekvivalence automatů s £-kroky a N FA Věta 2.48. Ke každému N FA M = (Q, E, 5, q0, F) s e-kroky existuje ekvivalentní NFA (bez e-kroků). Důkaz. Konstrukce M = (Q, S, 7, go, C) bez £-kroků: 7(5, a) = a) pro každé g G Q, a G S G = F pokud £>e(g0) n F = 0. FU{<7o} jinak. Korektnost: Dokážeme, že pro libovolné p G Q, w e Ľ+ platí 5(p, w) = 7(p, i/;) (indukcí vzhledem k délce slova w). Algoritmus □ IB102 Automaty, gramatiky a složitost, 7.10. 2013 13 Uzáverové vlastnosti regulárních jazyků Věta 2.49. a 2.51. Třída regulárních jazyků je uzavřená na sjednocení, průnik, rozdíl a komplement. Důkaz, synchronní paralelní kompozice automatů + komplement. □ Příklad. Lľ = {a*6V | 2i > j > 0} L2 = {a}*.{6}* L3 = {anbn | n > 0} L\ n Z/2 = L3 Jazyk Z/2 je regulární, L3 není regulární =^> Li není regulární. IB102 Automaty, gramatiky a složitost, 7.10.2013 14 Věta 2.52. Třída regulárních jazyků je uzavřená na zřetězení. Důkaz. Necht Li a L2 jsou regulární jazyky, rozpoznávané NFA M\ = (Qi, Ei, <5i, qi, Fi) a A42 = (Q2, E2, RE(Ľ) je parciální přechodová funkce. • I ^ Q je množina počátečních stavů. • ^ ^ Q je množina koncových stavů. IB102 Automaty, gramatiky a složitost, 7.10.2013 Příklad IB102 Automaty, gramatiky a složitost, 7.10.2013 Slovo w G E* je grafem Ai akceptováno, právě když • existuje posloupnost stavů qo,..., qni kde n > 0, qo £ I, qn £ F • a 5(qi-i,qi) je definováno pro každé 0 < i < n taková, že • w lze rozdělit na n částí w = v±.. .vn tak, že • £ L(S(qi-i,qi)) pro každé 0 < i < n. Slovo e je akceptováno také tehdy, je-li / nF^i. IB102 Automaty, gramatiky a složitost, 7.10. 2013 27 Převod regulárního přechodového grafu na N FA Motivace Věta 2.65. Pro libovolný regulární přechodový graf Ai — (Q, !<>F) existuje ekvivalentní NFA M1 s e-kroky. IB102 Automaty, gramatiky a složitost, 7.10. 2013 28 Důkaz. Algoritmus konstrukce N FA M1 s e-kroky. IB102 Automaty, gramatiky a složitost, 7.10.2013 29 Krok 1 Ke grafu M přidáme nový stav q0 a hranu q0 —» q pro každé q G I. Stav qo bude (jediným) počátečním stavem automatu M1', prvky F jeho koncovými stavy. IB102 Automaty, gramatiky a složitost, 7.10.2013 30 Krok 2 Opakovaně realizuj kroky (a) a (b) dokud přechodový graf obsahuje alespoň jednu hranu ohodnocenou symbolem, který nepatří do S U {e}, tedy je tvaru F + G, F.G, F* nebo 0. (a) Odstraň všechny hrany, které jsou ohodnoceny symbolem 0. (b) Vyber libovolnou hranu p —> q, kde E ^ S U {e}, odstraň ji a proved následující: IB102 Automaty, gramatiky a složitost, 7.10.2013 31 Konečnost algoritmu Ai obsahuje pouze konečně mnoho hran, tj. konečně mnoho regulárních výrazů. Každý regulární výraz obsahuje jen konečně mnoho výskytů +ř . a *. V každém kroku 2(b) jeden výskyt odstraníme. Korektnost algoritmu • Výsledný graf je přechodovým grafem nedeterministického konečného automatu M.' s e-kroky. • Přímo z definice regulárního přechodového grafu se snadno ověří, že kroky 1 a 2 popsaného transformačního algoritmu zachovávají ekvivalenci automatů, proto L(M) = L(Mf). □ IB102 Automaty, gramatiky a složitost, 7.10.2013 32