Rozšíření konečných automatů II Automaty s -kroky IB102 Automaty a gramatiky, 13. 10. 2008 1 Definice 2.46. Nedeterministický FA s -kroky je M = (Q, , , q0, 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í : Q × ( {}) 2Q . Rozšířená přechodová funkce Definujeme funkci D : Q 2Q následujícím předpisem. D(p) je nejmenší množina X Q taková, že platí: * p X, * pokud q X a r (q, ), pak také r X. Rozšíření funkce D na množiny stavů: pro Y Q položíme D(Y ) = qY D(q). IB102 Automaty a gramatiky, 13. 10. 2008 2 Příklad - výpočet D IB102 Automaty a gramatiky, 13. 10. 2008 3 Definice rozšířené přechodové funkce ^ : Q × 2Q * ^(q, ) = D(q), * ^(q, wa) = p^(q,w) D((p, a)). Lemma 2.47. V přechodovém grafu automatu M existuje cesta p1 . . . pm a q1 . . . qn, kde m, n 1, a , právě když qn ^(p1, a). Jazyk přijímaný automatem M s -kroky je L(M) = {w | ^(q0, w) F = }. IB102 Automaty a gramatiky, 13. 10. 2008 4 Příklad - výpočet rozříšeřené přechodové funkce pro automat s -kroky IB102 Automaty a gramatiky, 13. 10. 2008 5 Ekvivalence automatů s -kroky a NFA Věta 2.48. Ke každému NFA M = (Q, , , q0, F) s -kroky existuje ekvivalentní NFA (bez -kroků). Důkaz. Konstrukce M = (Q, , , q0, G) bez -kroků: (q, a) = ^(q, a) pro každé q Q, a G = F pokud D(q0) F = , F {q0} jinak. Korektnost: Dokážeme, že pro libovolné p Q, w + platí ^(p, w) = ^(p, w) (indukcí vzhledem k délce slova w). Algoritmus 2 IB102 Automaty a gramatiky, 13. 10. 2008 6 Uzávěrové 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. 2 Příklad. L1 = {ai bi cj | 2i j 0} L2 = {a} .{b} L3 = {an bn | n 0} L1 L2 = L3 Jazyk L2 je regulární, L3 není regulární = L1 není regulární. IB102 Automaty a gramatiky, 13. 10. 2008 7 Věta 2.52. Třída regulárních jazyků je uzavřená na zřetězení. Důkaz. Nechť L1 a L2 jsou regulární jazyky, rozpoznávané NFA M1 = (Q1, 1, 1, q1, F1) a M2 = (Q2, 2, 2, q2, F2), kde Q1 Q2 = . Definujeme NFA s -kroky M1 M2 = (Q1 Q2, 1 2, , q1, F2), kde = 1 2 {((p, ), {q2}) | p F1}. IB102 Automaty a gramatiky, 13. 10. 2008 8 Korektnost: Chceme dokázat L(M1 M2) = L(M1).L(M2) : Nechť u L(M1), tedy r F1 splňující r 1(q1, u). Nechť v L(M2), tedy 2(q2, v) F2 = . Pak ^(q1, uv) = p^(q1,u) ^(p, v) ^(r, v) ^(q2, v) = 2(q2, v). Protože 2(q2, v) F2 = , tak ^(q1, uv) F2 = . Tedy uv L(M1 M2). : 2 IB102 Automaty a gramatiky, 13. 10. 2008 9 Věta 2.53. Třída regulárních jazyků je uzavřená na iteraci. Důkaz. Nechť L je regulární jazyk akceptovaný NFA M = (Q, , , q0, F). Definujeme NFA s -kroky M = (Q {p}, , , p, {p}), kde p Q a = {((p, ), {q0}} {((q, ), {p}) | q F}. 2 IB102 Automaty a gramatiky, 13. 10. 2008 10 Uzávěrové vlastnosti regulárních jazyků - Shrnutí IB102 Automaty a gramatiky, 13. 10. 2008 11 Regulární výrazy Definice 2.58. Množina regulárních výrazů nad abecedou , označovaná RE(), je definována induktivně takto: 1. , a aaa pro každé a jsou regulární výrazy nad (tzv. základní regulární výrazy). 2. Jsou-li E, F regulární výrazy nad , jsou také (E.F), (E +F) a (E ) regulární výrazy nad . 3. Každý regulární výraz vznikne po konečném počtu aplikací kroků 1­2. IB102 Automaty a gramatiky, 13. 10. 2008 12 Každý regulární výraz E nad abecedou popisuje (jednoznačně určuje) jazyk L(E) nad abecedou podle těchto pravidel: L() def = {} L() def = L(aaa) def = {a} pro každé a L( E.F ) def = L(E).L(F) L( E + F ) def = L(E) L(F) L( E ) def = L(E) IB102 Automaty a gramatiky, 13. 10. 2008 13 Příklady IB102 Automaty a gramatiky, 13. 10. 2008 14 Ekvivalence konečných automatů a reg. výrazů 76 54 01 23 RE 76 54 01 23 DFA 76 54 01 23 NFA Věta 2.43 oo 76 54 01 23 NFA s -kroky Věta 2.48 oo Věta 2.60. Nechť E je regulární výraz. Pak existuje konečný automat rozpoznávající L(E). Důkaz. Pro libovolnou abecedu lze zkonstruovat konečné automaty, které rozpoznávají jazyky popsané základními regulárními výrazy, tj. , {} a {a} pro každé a . 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. 2 IB102 Automaty a gramatiky, 13. 10. 2008 15 Příklad IB102 Automaty a gramatiky, 13. 10. 2008 16 76 54 01 23 RE 76 54 01 23 DFA 76 54 01 23 NFA Věta 2.43 oo 76 54 01 23 NFA s -kroky Věta 2.48 oo Věta 2.62. Nechť 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, 13. 10. 2008 17