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, 24.10. 2011 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ů. • S je vstupní abeceda. • 5 : Q x Q —> 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 a gramatiky, 24.10. 2011 Příklad IB102 Automaty a gramatiky, 24.10. 2011 3 Slovo w G S* je grafem M akceptováno, právě když • existuje posloupnost stavů qo,..., qn, 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 i... vn tak, že • L{S{Qí-uQí)) Pro každé 0 < i < n. Slovo 5 je akceptováno také tehdy, je-li I n F ^ 0. IB102 Automaty a gramatiky, 24.10. 2011 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 Ai — (Q, !<>F) existuje ekvivalentní NFA M1 s e-kroky. IB102 Automaty a gramatiky, 24.10. 2011 5 Důkaz. Algoritmus konstrukce N FA M1 s e-kroky. IB102 Automaty a gramatiky, 24.10. 2011 6 Krok 1 Ke grafu M přidáme nový stav q0 a hranu q0 —> q pro každé q e I. Stav qo bude (jediným) počátečním stavem automatu Mf, prvky F jeho koncovými stavy. IB102 Automaty a gramatiky, 24.10. 2011 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 ^ S U {e}, odstraň ji a proved následující: IB102 Automaty a gramatiky, 24.10. 2011 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 M1 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 a gramatiky, 24.10. 2011 9 Převod D FA na regulární přechodový graf Motivace Věta 2.66. Pro každý regulární přechodový graf M. (Q, 1,F) existuje ekvivalentní regulární přechodový graf M1 ({x, y}, E, 5', {?/}), kde 5' může být definováno pouze pro dvoj (x,y). IB102 Automaty a gramatiky, 24.10. 2011 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, 24.10.2011 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, 24.10. 2011 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, 24.10. 2011 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, 24.10. 2011 14 Převod regulární gramatiky na konečný automat Lemma 2.69. Ke každé regulární gramatice Q — (iV, S, P, S) existuje nedeterministický konečný automat Ai = (Q,Y,,S,qo,F) takový, že L(g) = L(M). Důkaz. IB102 Automaty a gramatiky, 24.10. 2011 15 Konstrukce konečného automatu • Q = {Ä I A G N} U {qf}, kde ?/ £ iV. • aB je pravidlo v P, pak B G a). - Pokud A —t a je pravidlo v P, kde a ^ e, pak G a) Í{S, qf} pokud S —> £ je pravidlo v P, {g/} jinak. IB102 Automaty a gramatiky, 24.10. 2011 16 Korektnost Nejprve indukcí vzhledem ke k dokážeme, že pro každé ai,..., ak G E a B G N platí 5 di... <=^> B G 5(5, ai... a^). • Základní krok k = 0: Z definice 5 plyne 5(5, e) = {5}. Proto 5^* B 4=^ B = S ^ B = Š <=^> Beô(Š,e) • Indukční krok: 5 CL\ . . . CLk+lB 3C G iV takové, že 5 =^>* ai... a^C ai... ctk+iB <^ 3C G N takové, že C G 5(5 ) A C -» dk+iB 3C e N takové, že C G 5(5, ai... ak) A Š G 5(C, ak+i) <^> B G 5(5, a\... afc+i). IB102 Automaty a gramatiky, 24.10. 2011 17 Dokázali jsme: S^*ai...akB <^=> B G ô(S, a\... a&) Ukážeme, že ty G L(G) w G L(VW): w = e\ ii; = m, kde t; G S*ř a G S: m G L(í?) S =>* i;S => S ^* vB a B ^ a e P B G <í(5,í;) a g/ G 5(B,a) qf m G L(X) <; s / \ < > / \ <; > s / \ v- —ŕ IB102 Automaty a gramatiky, 24.10. 2011 Převod konečného automatu na regulární gramatiku Lemma 2.71 Pro každý konečný automat M = (Q, E, č, q0, F) existuje regulární gramatika Q = (iV, E, P, 5) taková, že L(M) = L(Q). Důkaz. IB102 Automaty a gramatiky, 24.10. 2011 19 Bez újmy na obecnosti předpokládejme, že Ai je nedeterministický. • N = {q I q G Q} U {S}, kde S £ Q. • P je nejmenší množina pravidel splňující: - Pokud p G S(q, a), \eq —> áp pravidlo v P. - Pokud p G S(q, a) a p G F, je g —>> a pravidlo v P. - Pokud p G ô(qo, a), je S —> áp pravidlo v P. - Pokud p G ô(qo, a) a p G F, je 5 —>> a pravidlo v P. - Pokud qo G F, je S —> e pravidlo v P. Gramatika Q = (iV, E, P, 5) je zřejmě regulární. Platí: S(qo, Q>i • • • &/c) nf ^ 0, kde fc > 0, ai,..., a& e £ IB102 Automaty a gramatiky, 24.10. 2011 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 S ekvivalence: jsou M a Mr ekvivalentní? (platí L(M)=L(Mr) ?) inkluze (jazyků): platí L(M) C L (M') ? příslušnost (slova k jazyku): je-li dáno w £ S*ř platíc £ ? prázdnost (jazyka): je L(AÍ) = 0 ? univerzalita (jazyka): je L(AÍ) = E* ? konečnost (jazyka): je konečný jazyk? IB102 Automaty a gramatiky, 24.10. 2011 21 Věta 2.74 Problém prázdnosti (L(A4) = 0) a problém univerzality (L(M) = £*) jsou rozhodnutelné pro regulární jazyky. Důkaz. L(M) je prázdný, právě když mezi dosažitelnými stavy automatu Ai 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é í/i,L2 platí: (Li = L2) (Li n co-L2) U (co-Li n L2) = 0. Pro Li, í/2 zadané automaty lze uvedené operace algoritmicky realizovat. Alternativně: minimalizace a kanonizace. □ IB102 Automaty a gramatiky, 24.10. 2011 22 Věta 2.76 Problém, zda jazyk L zadaný automatem Ai 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í \xz\ > n. Pokud \xz\ > 2n, celý postup opakujeme. (<=) \w\ > n, pak Ai na w musí projít dvakrát stejným stavem. Proto w = xyz tak, že \y\ > 1 a platí 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, 24.10. 2011 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šírené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, 24.10. 2011 24