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, 22.10.2012 1 Regulární přechodový graf Definice 2.64. Regulární přechodový graf M je pětice (Q, E, 5, /, F), • Q je neprázdná konečná množina stavů. • E je vstupní abeceda. • S : Q x Q —> RE(Ľ) je parciální přechodová funkce. • I Q Q Je množina počátečních stavů. • F Q Q je množina koncových stavů. IB102 Automaty a gramatiky, 22.10.2012 Příklad IB102 Automaty a gramatiky, 22.10.2012 3 Slovo w G E* je grafem M, akceptováno, právě když • existuje posloupnost stavů go? • • • ? Qn, kde n>0,qo£l,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 • Vi G L(5(qi-i,qi)) pro každé 0 < z < n. Slovo s je akceptováno také tehdy, je-li IB102 Automaty a gramatiky, 22.10. 2012 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, E, 5, /, F) existuje ekvivalentní NFA M1 s s-kroky. IB102 Automaty a gramatiky, 22.10. 2012 5 Důkaz. Algoritmus konstrukce NFA M.' s s-kroky. IB102 Automaty a gramatiky, 22.10.2012 6 Krok 1 Ke grafu M přidáme nový stav qQ a hranu q0 -> q pro každé q G /. Stav q0 bude (jediným) počátečním stavem automatu Mř, prvky F jeho koncovými stavy. IB102 Automaty a gramatiky, 22.10.2012 7 Krok 2 Opakovaně realizuj kroky (a) a (b) dokud přechodový graf obsahuje alespoň jednu hranu ohodnocenou symbolem, který nepatří do E 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 E U {s}, odstraň ji a proved následující: IB102 Automaty a gramatiky, 22.10.2012 8 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 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(M) = L(M!). □ IB102 Automaty a gramatiky, 22.10.2012 9 Převod D FA na regulární přechodový graf Motivace Věta 2.66. Pro každý regulární přechodový graf A4 (Q, E, 5, /, F) existuje ekvivalentní regulární přechodový graf M! ({#, ?/}, E, 5', {x}, {?/}), kde 5' může být definováno pouze pro dvoj IB102 Automaty a gramatiky, 22.10.2012 Důkaz. Algoritmus transformace Krok 1 Ke grafu M 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, 22.10.2012 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. IB102 Automaty a gramatiky, 22.10.2012 12 Po odstranění všech stavů různých od x a 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, 22.10.2012 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, 22.10.2012 14 Převod regulární gramatiky na konečný automat Lemma 2.69. Ke každé regulární gramatice Q = (TV, E, P, S) existuje nedeterministický konečný automat M = (Q, E, 5, qo,F) takový, že L(G) = L(M). Důkaz. IB102 Automaty a gramatiky, 22.10.2012 15 Konstrukce konečného automatu • Q = {Ä I A G N} U {g/}, kde g/ 0 TV. • > 2^ splňující: - Pokud A —>> aS je pravidlo v P, pak S G a). - Pokud A a je pravidlo v P, kde a ^ e, pak qf G a) Í{5, qf} pokud S —> e je pravidlo v P, {g/} jinak. IB102 Automaty a gramatiky, 22.10.2012 16 Korektnost Nejprve indukcí vzhledem ke k dokážeme, že pro každé ai,..., ak g E a S g N platí 5 ai... CLkB B g 5(5, ai... a/~). • Základní krok k = 0: Z definice 5 plyne 5(5,s) = {S}. Proto 5 S ^ 5 = 5 5 = 5 4=> £g5(5,č) • Indukční krok: 5 ai... cLk+iB 3C g AT takové, že 5 =4>* ai... akC ai... dk+iB 3C e N takové, že C g 5(5, ai... afc) a C -> ak+1B 3C g N takové, že Č g 5(5, ai... ak) a B g 5(C, a^+i) S g 5(5, ai... afc+i). IB102 Automaty a gramatiky, 22.10.2012 17 Dokázali jsme: 5^*a:L...a/cB B G 5(5, a\... a&) Ukážeme, že w G L(ŕ/) «4=^> w G L (.M): w = s: w = va, kde v G S*, a G S: G L((?) 5 S ^* vB A B ^ a G P ^ Bé <5(5, v) A g/ G 5(5, a) IB102 Automaty a gramatiky, 22.10.2012 Převod konečného automatu na regulární gramatiku Lemma 2.71 Pro každý konečný automat M = (Q, S, 5, qo, F) existuje regulární gramatika Q — (N, E, P, S) taková, že L (M) = L(Q). Důkaz. IB102 Automaty a gramatiky, 22.10.2012 19 Bez újmy na obecnosti předpokládejme, že Ai je nedeterministický. • N = {q I q G Q] U {5}, kde S 0 Q. • P je nejmenší množina pravidel splňující: - Pokud p G a), je q áp pravidlo v P. - Pokud p G 5(q, a) a p G F, je g —>> a pravidlo v P. - Pokud p G 5(go? o)i je S áp pravidlo v P. - Pokud p G S(qo, a) a p E F, }e S —> a pravidlo v P. - Pokud qo G F, je 5 —>* s pravidlo v P. Gramatika C/ = (TV, E, P, 5) je zřejmě regulární. /\ Platí: ô(qo, a\... a^) kde fe > 0,oi,...,Ofe G S 5 CLi . . . CLk IB102 Automaty a gramatiky, 22.10.2012 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 Ai a M! nad E ekvivalence: jsou M a M! ekvivalentní? (platí L(M)=L(M') ?) inkluze (jazyků): platí L{M) C L{M') ? příslušnost (slova k jazyku): je-li dáno w G E*, platí w G L(A^) ? prázdnost (jazyka): je L(A/Í) = 0 ? univerzalita (jazyka): je L(A/Í) = E* ? konečnost (jazyka): je L(Q) konečný jazyk? IB102 Automaty a gramatiky, 22.10.2012 21 Věta 2.74 Problém prázdnosti (L(M) = 0) a problém univerzality (L(Ai) = E*) jsou rozhodnutelné pro regulární jazyky. Důkaz. L(Ai) je prázdný, právě když mezi dosažitelnými stavy automatu Ai není žádný koncový stav. Univerzalita: L(M) = E* ^ co-L(M) = 0. □ Věta 2.77 Problém ekvivalence je rozhodnutelný pro regulární jazyky. Důkaz. Pro libovolné Li,L2 platí: (Li = 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, 22.10.2012 22 Věta 2.76 Problém, zda jazyk L zadaný automatem A4 je konečný, resp. nekonečný, je rozhodnutelný. Důkaz. Necht Ai je DFA. L je nekonečný právě když Ai akceptuje alespoň jedno slovo w G E* 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. Necht \u\ > 2n. Z lemma o vkládání plyne, že u = xyz, kde 1 < \y\ < n a xz G L. Platí |x2:| > n. Pokud \xz\ > 2n, celý postup opakujeme. (<(=) \w\ > n, pak na w musí projít dvakrát stejným stavem. Proto w = xyz tak, že |y| > 1 a platí xy%z G L pro každé z 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, 22.10.2012 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, f lex) 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, 22.10.2012 24