Rozšírení konečných automatů II Automaty s e-kroky IB102 Automaty a gramatiky, 17.10.2011 1 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 a gramatiky, 17.10.2011 2 Příklad - výpočet D IB102 Automaty a gramatiky, 17.10.2011 3 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 a gramatiky, 17.10.2011 Příklad - výpočet rozříseřené přechodové funkce pro automat s e-kroky IB102 Automaty a gramatiky, 17.10.2011 5 Ekvivalence automatů s e-kroky a N FA Věta 2.48. Ke každému N FA M = (Q, S, 5, q0, F) s e-kroky existuje ekvivalentní NFA (bez e-kroků). Důkaz. Konstrukce M = (Q, S, 7, go, C) bez e-kroků: 7(5, a) = a) pro každé geQ,ačS G = F pokud £>e(g0) n F = 0. FU{g0} jinak. Korektnost: Dokážeme, že pro libovolné p G Q, w G E+ platí 5(p, w) = 7(p, i/;) (indukcí vzhledem k délce slova w). Algoritmus □ IB102 Automaty a gramatiky, 17.10. 2011 6 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 a gramatiky, 17.10.2011 7 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, 5i, Fi) a A42 = (Q2, E2, ) ^ 5(r,v) 3 S(q2,v) = 52(g2 peá(gi,ií) Protože ô2{q2, v)HF2^ 0, tak %i, uv) n F2 ^ 0. Tedy wt> G L(Mi 0 -M2). C: IB102 Automaty a gramatiky, 17.10.2011 Věta 2.53. Třída regulárních jazyků je uzavřená na iteraci. Důkaz. Necht L je regulární jazyk akceptovaný NFA M = (Q, S, ô, qo, F). Definujeme NFA s e-kroky M* = (Q U {p}, Ti, ô',p, {p}), kde p ^ Q 6' = 6U {((p, e), {q0}} U {((q, e), {p}) | g G F}. IB102 Automaty a gramatiky, 17.10.2011 Uzáverové vlastnosti regulárních jazyků - Shrnutí IB102 Automaty a gramatiky, 17.10.2011 11 Regulární výrazy Definice 2.58. Množina regulárních výrazů nad abecedou E, označovaná RE(Yi), je definována induktivně takto: 1. e, 0 a a pro každé a £ E jsou regulární výrazy nad S fŕzy. základní regulární výrazy). 2. Jsou-li E,F regulární výrazy nad S, jsou také (E.F),(E + F) a regulární výrazy nad S. 3. Každý regulární výraz vznikne po konečném počtu aplikací kroků 1-2. IB102 Automaty a gramatiky, 17.10.2011 12 Každý regulární výraz E nad abecedou S popisuje (jednoznačně určuje) jazyk L (E) nad abecedou S podle těchto pravidel: m a {e} L(0) ^ 0 L(a) = {a} pro každé a G E L(£.F) =7 L(E).L(F) L(E + F) = L(E)UL(F) L(E*) =7 L{E)* IB102 Automaty a gramatiky, 17.10.2011 13 Příklady IB102 Automaty a gramatiky, 17.10.2011 Ekvivalence konečných automatů a reg. výrazů DFA Věta 2.43 N FA Věta 2.48 Věta 2.60. Necht E je regulární výraz. Pak existuje konečný automat rozpoznávající L(E). Důkaz. Pro libovolnou abecedu S lze zkonstruovat konečné automaty, které rozpoznávají jazyky popsané základními regulárními výrazy, tj. 0, {e} a {a} pro každé a £ S. Tvrzení věty pak plyne z uzavřenosti jazyků rozpoznatelných konečnými automaty vůči operacím sjednocení, zřetězení a iteraci. □ IB102 Automaty a gramatiky, 17.10.2011 15 Příklad IB102 Automaty a gramatiky, 17.10.2011 D FA Věta 2.43 N FA Věta 2.48 r s NFA s e-kroky Věta 2.62. Necht L je akceptovaný nějakým DFA, pak L je popsatelný nějakým regulárním výrazem. Důkaz bude podán později pomocí regulárních přechodových grafů. Kleeneho věta 2.63. Libovolný jazyk je popsatelný regulárním výrazem právě když je rozpoznatelný konečným automatem. Ekvivalentní formulace: Třída jazyků rozpoznatelných konečnými automaty je nejmenší třída, která obsahuje všechny konečné množiny a je uzavřena na sjednocení, zřetězení a iteraci. IB102 Automaty a gramatiky, 17.10.2011 17