Věta 2.60 DFA Věta 2.43 NFA Věta 2.48 NFA s e-kroky Kleeneho věta 2.63. Libovolný jazyk je popsatelný regulárním výrazem právě když je rozpoznatelný konečným automatem. IB102 Automaty a gramatiky, 2.11.2009 1 Regulární přechodový graf Definice 2.64. Regulární přechodový graf M je pětice (Q, £, 5, /, F), • Q je neprázdná konečná množina stavů. • S je vstupní abeceda. • ô : Q x Q —» RE(Ľ) je parciální přechodová funkce. • ^ ^ Q je množina počátečních stavů. • F ^ Q je množina koncových stavů. IB102 Automaty a gramatiky, 2.11.2009 Příklad IB102 Automaty a gramatiky, 2.11.2009 3 Slovo w G S* je grafem A4 akceptováno, právě když • existuje posloupnost stavů go? • • • ? 9m kde n > 0, qo £ I, qn £ F • a S(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 • i>i £ L(ö(qi-i,qi)) pro každé 0 < i < n. Slovo £ je akceptováno také tehdy, je-li JnF^ř). IB102 Automaty a gramatiky, 2.11. 2009 4 Převod regulárního přechodového grafu na N FA Motivace Věta 2.65. Pro libovolný regulární přechodový graf A4 = (Q, £, 5, /, F) existuje ekvivalentní N FA A4' s £-kroky. IB102 Automaty a gramatiky, 2.11.2009 5 Důkaz. Algoritmus konstrukce NFA A4' s £-kroky. IB102 Automaty a gramatiky, 2.11.2009 6 Krok 1 Ke grafu A4 přidáme nový stav q0 a hranu qo ^ q pro každé q £ I. Stav go bude (jediným) počátečním stavem automatu A4\ prvky F jeho koncovými stavy. IB102 Automaty a gramatiky, 2.11.2009 7 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 0 S U {e}, odstraň ji a proved následující: F+G F G F.G F * F G IB102 Automaty a gramatiky, 2.11.2009 8 Konečnost algoritmu A4 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 A4' s £-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 (A4) = L(AÍ'). D IB102 Automaty a gramatiky, 2.11.2009 9 Převod DFA na regulární přechodový graf Motivace Věta 2.66. Pro každý regulární přechodový graf A4 = (Q, E, 5,1,F) existuje ekvivalentní regulární přechodový graf M* = ({#,?/}, E, 5', {#}, {y}), kde 5' může být definováno pouze pro dvojici (x,y). IB102 Automaty a gramatiky, 2.11.2009 10 Důkaz. Algoritmus transformace Krok 1 Ke grafu A4 přidáme nový počáteční stav x a nový koncový stav y. Přidáme také hrany x —» q pro každé q G I a r —» y pro každé r G F. IB102 Automaty a gramatiky, 2.11.2009 11 Krok 2 Každý stav p různý od x,y nyní odstraníme spolu s hranami, které do p vcházejí nebo z p vycházejí. Pokud do p nevede hrana z jiného uzlu, je nedosažitelný z počátečního stavu. Pokud z p nevede hrana do jiného uzlu, nelze z p dosáhnout koncový stav. V obou případech p odstraníme bez náhrady. Pro každou dvojici vstupní hrany vedoucí do p z jiného uzlu a výstupní hrany vedoucí z p do jiného uzlu přidáme přímý přechod. Pak p odstraníme. í r )-----------{ p )----------->l q ) => t r )--------------------------->( q ) E ŕ^\ F /^\ G /^\ /^\ F.E*.G /^\ r -------{ p -------{ q => r -----------------{ q IB102 Automaty a gramatiky, 2.11.2009 12 "~x F1.(E+®)*.G1 x~x r\ j------------------{ qi ) ^\ /F2.(E+Q)* .G± // \Fl.OE+0)*.G2 ^2 )---------------------( 0.2 ) _y f2.(f+0)*.g2 v_y Po odstranění všech stavů různých od x 3 y zůstanou tyto dva stavy spolu s (žádnou nebo jednou) hranou z x do y. Konečnost algoritmu Každým krokem 2 snížíme počet stavů. Korektnost algoritmu Z definice regulárního přechodového grafu přímo ověříme, že kroky 1 i 2 zachovávají ekvivalenci. □ IB102 Automaty a gramatiky, 2.11.2009 13 Ekvivalence konečných automatů a regulárních gramatik Pojem regulárního jazyka byl definován dvakrát - nejprve pomocí regulární gramatiky a pak ještě jednou pomocí konečného automatu. IB102 Automaty a gramatiky, 2.11.2009 14 Převod regulární gramatiky na konečný automat Lemma 2.69. Ke každé regulární gramatice Q = (TV, £, P, S) existuje nedeterministický konečný automat A4 = (Q,S,5, qo,F) takový, že L(G) = L(M). Důkaz. IB102 Automaty a gramatiky, 2.11.2009 15 Konstrukce konečného automatu • Q = {Ä I A G N} U {g/}, kde qf 0 N. • q0 = S. • 5 je nejmenší funkce Q x S —» 2^ splňující: - Pokud A —> aß je pravidlo v P, pak P G 5(A, a). - Pokud A —» a je pravidlo v P, kde a ^ e, pak gj G 5(A, a) {{5, g/} pokud S —> e je pravidlo v P, {g/} jinak. IB102 Automaty a gramatiky, 2.11.2009 16 55 Korektnost Nejprve indukcí vzhledem ke k dokážeme, že pro každé ßi, • • • ? ak £ S a B G N platí o =>- cii... cik-B * 3C G TV takové, že 5 =^>* ai... akC => ai... ctk+iB > 3C G N takové, že C G 5(5, ai... a&) A C —> ak+iB > 3C e N takové, že C G 5(5, ai... ak) A B G 5(C, ak+1) $- B G 5(5, dl... čifc_|_i). IB102 Automaty a gramatiky, 2.11.2009 17 Dokázali jsme: S =,>* a\... a^B <^> B G 5(5, ai... a&) Ukážeme, že w G L((?) ^^ w G L(7W): w = e\ eeL(G) ^^s^eeP^^SeF^^ e e L(M) w = va, kde i; G S*, a G S: m G L(C?) <^=> 5 =>* vB => va S ^* vB A B ^ae P N 7 N 7 \7 Be 6(Š,v) A qf G 5(B,a) qf e 5(S,va) <=> va e L(M) D IB102 Automaty a gramatiky, 2.11.2009 18 Převod konečného automatu na regulární gramatiku Lemma 2.71 Pro každý konečný automat Aí = (Q, S, 5, go? F) existuje regulární gramatika Q = (TV, S, P, S) taková, že L (Al) = £(£/)■ Důkaz. IB102 Automaty a gramatiky, 2.11.2009 19 Bez újmy na obecnosti předpokládejme, že A4 je nedeterministický. • N = {q I q G Q} U {S}, kde S 0 Q. • P je nejmenší množina pravidel splňující: - Pokud p G 5(g, a), je g —» ap pravidlo v P. - Pokud p G 5(g, a) a p G P, je q —» a pravidlo v P. - Pokud p G 5( ap pravidlo v P. - Pokud p G 5(go? o) a p G P, je 5 ^ a pravidlo v P. - Pokud qo £ F, je S ^ e pravidlo v P. Gramatika Q = (TV, S, P, 5) je zřejmě regulární. /\ Platí: 5( 0, ai,..., a^ G S IB102 Automaty a gramatiky, 2.11.2009 20 55 Rozhodnutelné problémy pro třídu reg. jazyků Regulární jazyk - popsaný některým z uvažovaných formalismů. Otázky: Máme-li dány konečné automaty Aí a Ať nad S ekvivalence: jsou M a Ať ekvivalentní? (platí L(M)=L(Mf) ?) inkluze (jazyků): platí L(M) C L(Ať) ? příslušnost (slova k jazyku): je-li dáno w £ S*, platí w G L (Al) ? prázdnost (jazyka): je L(AÍ) = 0 ? univerzalita (jazyka): je L(AÍ) = S* ? konečnost (jazyka): je L(^) konečný jazyk? IB102 Automaty a gramatiky, 2.11.2009 21 Věta 2.74 Problém prázdnosti (L(M) = 0) a problém univerzality ? (L(AÍ) = £*) jsou rozhodnutelné pro regulární jazyky. Důkaz. L (A4) je prázdný, právě když mezi dosažitelnými stavy automatu A4 není žádný koncový stav. Univerzalita: L(M) = S* ^^ co-L(M) = 0. □ Věta 2.77 Problém ekvivalence je rozhodnutelný pro regulární jazyky. Důkaz. Pro libovolné L\^L2 platí: (L1 = L2) ^^ (Li n co-L2) U (co-Li n L2) = 0. Pro Li, L2 zadané automaty lze uvedené operace algoritmicky realizovat. Alternativně: minimalizace a kanonizace. □ IB102 Automaty a gramatiky, 2.11.2009 22 Věta 2.76 Problém, zda jazyk L zadaný automatem A4 je konečný, resp. nekonečný, je rozhodnutelný. Důkaz. Necht A4 je DFA. L je nekonečný právě když A4 akceptuje alespoň jedno slovo wjgE* s vlastností n < \w\ < 2n, kde n = card(Q). (^=^) L nekonečný, pak existuje u G L takové, že \u\ > n. Je-li \u\ < 2n, jsme hotovi. Jinak z lemma o vkládání plyne, že u = xyz, kde 1 < \y\ < n a xz G L. Platí \xz\ > n. Pokud \xz\ > 2n, celý postup opakujeme. (<==) \w\ > n, pak A4 na w musí projít dvakrát stejným stavem. Proto w = xyz tak, že \y\ > 1 a platí x?/^ G L pro každé i G No (viz důkaz lemmatu o vkládání), tedy L je nekonečný. Existenci w G L takového, že n < \w\ < 2n, lze algoritmicky ověřit (slov je konečně mnoho, "vyzkoušíme" každé z nich). □ IB102 Automaty a gramatiky, 2.11.2009 23 Aplikace reg. jazyků a konečných automatů vyhledávání vzorů (pattern matching) v textu (editory, textové systémy), DNA sekvencích, . . . Například v Unixu: grep - vyhledávání podle zadaného regulárního výrazu egrep - vyhledávání podle zadaného rozšířeného regulárního výrazu f grep - vyhledávání podle zadaného řetězce Zpracování lexikálních jednotek například při automatizované konstrukci překladačů (lex, flex) Zpracování obrazů (image processing) Konečné automaty nad nekonečnými slovy Specifikace a verifikace konečně stavových systémů Konečné automaty s výstupem IB102 Automaty a gramatiky, 2.11.2009 24