76 54 01 23 RE 76 54 01 23 DFAoo 76 54 01 23 NFA Věta 2.43 oo 76 54 01 23 NFA s -kroky Věta 2.48 oo ED GF Věta 2.60 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, 20. 10. 2008 1 Regulární přechodový graf Definice 2.64. Regulární přechodový graf M je pětice (Q, , , I, F), kde * Q je neprázdná konečná množina stavů. * je vstupní abeceda. * : Q × Q RE() je parciální přechodová funkce. * I Q je množina počátečních stavů. * F Q je množina koncových stavů. IB102 Automaty a gramatiky, 20. 10. 2008 2 Příklad IB102 Automaty a gramatiky, 20. 10. 2008 3 Slovo w je grafem M akceptováno, právě když * existuje posloupnost stavů q0, . . . , qn, kde n 1, q0 I, qn F * a (qi-1, qi) je definováno pro každé 0 < i n taková, že * w lze rozdělit na n částí w = v1 . . . vn tak, že * vi L((qi-1, qi)) pro každé 0 < i n. Slovo je akceptováno také tehdy, je-li I F = . IB102 Automaty a gramatiky, 20. 10. 2008 4 Převod regulárního přechodového grafu na NFA Motivace Věta 2.65. Pro libovolný regulární přechodový graf M = (Q, , , I, F) existuje ekvivalentní NFA M s -kroky. IB102 Automaty a gramatiky, 20. 10. 2008 5 Důkaz. Algoritmus konstrukce NFA M s -kroky. IB102 Automaty a gramatiky, 20. 10. 2008 6 Krok 1 Ke grafu M přidáme nový stav q0 a hranu q0 q pro každé q I. Stav q0 bude (jediným) počátečním stavem automatu M , prvky F jeho koncovými stavy. IB102 Automaty a gramatiky, 20. 10. 2008 7 Krok 2 Opakovaně realizuj kroky (a) a (b) dokud přechodový graf obsahuje alespoň jednu hranu ohodnocenou symbolem, který nepatří do {}, tedy je tvaru F + G, F.G, F nebo . (a) Odstraň všechny hrany, které jsou ohodnoceny symbolem . (b) Vyber libovolnou hranu p E q, kde E {}, odstraň ji a proveď následující: onmlhijkp F +G //onmlhijkq = onmlhijkp F // G // onmlhijkq onmlhijkp F.G //onmlhijkq = onmlhijkp F //onmlhijk s G //onmlhijkq onmlhijkp F //onmlhijkq = onmlhijkp //onmlhijk s // [\ _^]F onmlhijkq IB102 Automaty a gramatiky, 20. 10. 2008 8 Konečnost algoritmu M obsahuje pouze konečně mnoho hran a každý regulární výraz vznikne aplikací pravidel 1­2 z definice regulárních výrazů (2.58) v konečně mnoha krocích. Korektnost algoritmu * Výsledný graf je přechodovým grafem nedeterministického konečného automatu M 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 ). 2 IB102 Automaty a gramatiky, 20. 10. 2008 9 Převod DFA na regulární přechodový graf Motivace Věta 2.66. Pro každý regulární přechodový graf M = (Q, , , I, F) existuje ekvivalentní regulární přechodový graf M = ({x, y}, , , {x}, {y}), kde může být definováno pouze pro dvojici (x, y). IB102 Automaty a gramatiky, 20. 10. 2008 10 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 I a r y pro každé r F. IB102 Automaty a gramatiky, 20. 10. 2008 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. Pokud do p vchází hrana z jiného uzlu a také z p vychází hrana do jiného uzlu, postupujeme následovně: onmlhijkr1 F1 %%ttttttttttttttttt onmlhijkq1 onmlhijkp G1 99ttttttttttttttttt G2 %%ttttttttttttttttt [\ _^] E 0000 onmlhijkr2 F2 99ttttttttttttttttt onmlhijkq2 - onmlhijkr1 F1.(E+) .G1 // F1.(E+) .G2 ##qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq onmlhijkq1 onmlhijkr2 F2.(E+) .G2 // F2.(E+) .G1 ;;wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww onmlhijkq2 IB102 Automaty a gramatiky, 20. 10. 2008 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. 2 IB102 Automaty a gramatiky, 20. 10. 2008 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, 20. 10. 2008 14 Převod regulární gramatiky na konečný automat Lemma 2.69. Ke každé regulární gramatice G = (N, , P, S) existuje nedeterministický konečný automat M = (Q, , , q0, F) takový, že L(G) = L(M). Důkaz. IB102 Automaty a gramatiky, 20. 10. 2008 15 Konstrukce konečného automatu * Q = {A | A N} {qf}, kde qf N. * q0 = S. * je nejmenší funkce Q × 2Q splňující: ­ Pokud A aB je pravidlo v P, pak B (A, a). ­ Pokud A a je pravidlo v P, kde a = , pak qf (A, a) * F = {S, qf} pokud S je pravidlo v P, {qf} jinak. IB102 Automaty a gramatiky, 20. 10. 2008 16 Korektnost Nejprve indukcí vzhledem ke k dokážeme, že pro každé a1, . . . , ak a B N platí S a1 . . . akB B ^(S, a1 . . . ak). * Základní krok k = 0: Z definice ^ plyne ^(S, ) = {S}. Proto S B B = S B = S B ^(S, ) * Indukční krok: S a1 . . . ak+1B C N takové, že S a1 . . . akC a1 . . . ak+1B C N takové, že C ^(S, a1 . . . ak) C ak+1B C N takové, že C ^(S, a1 . . . ak) B (C, ak+1) B ^(S, a1 . . . ak+1). IB102 Automaty a gramatiky, 20. 10. 2008 17 Dokázali jsme: S a1 . . . akB B ^(S, a1 . . . ak) Ukážeme, že w L(G) w L(M): * w = : L(G) S P S F L(M) * w = va, kde v , a : va L(G) S vB va S vB B a P B ^(S, v) qf (B, a) qf ^(S, va) va L(M) 2 IB102 Automaty a gramatiky, 20. 10. 2008 18 Převod konečného automatu na regulární gramatiku Lemma 2.71 Pro každý konečný automat M = (Q, , , q0, F) existuje regulární gramatika G = (N, , P, S) taková, že L(M) = L(G). Důkaz. IB102 Automaty a gramatiky, 20. 10. 2008 19 Bez újmy na obecnosti předpokládejme, že M je nedeterministický. * N = {q | q Q} {S}, kde S Q. * P je nejmenší množina pravidel splňující: ­ Pokud p (q, a), je q ap pravidlo v P. ­ Pokud p (q, a) a p F, je q a pravidlo v P. ­ Pokud p (q0, a), je S ap pravidlo v P. ­ Pokud p (q0, a) a p F, je S a pravidlo v P. ­ Pokud q0 F, je S pravidlo v P. Gramatika G = (N, , P, S) je zřejmě regulární. Platí: ^(q0, a1 . . . ak) F = , kde k 0, a1, . . . , ak S a1 . . . ak 2 IB102 Automaty a gramatiky, 20. 10. 2008 20 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 M a M nad ekvivalence: jsou M a M ekvivalentní? (platí L(M)=L(M ) ?) inkluze (jazyků): platí L(M) L(M ) ? příslušnost (slova k jazyku): je-li dáno w , platí w L(M) ? prázdnost (jazyka): je L(M) = ? univerzalita (jazyka): je L(M) = ? konečnost (jazyka): je L(G) konečný jazyk? IB102 Automaty a gramatiky, 20. 10. 2008 21 Věta 2.74 Problém prázdnosti (L(M) ? = ) 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 M není žádný koncový stav. Univerzalita: L(M) = co­L(M) = . 2 Věta 2.77 Problém ekvivalence je rozhodnutelný pro regulární jazyky. Důkaz. Pro libovolné L1, L2 platí: (L1 =L2) (L1 co­L2) (co­L1 L2) = . Pro L1, L2 zadané automaty lze uvedené operace algoritmicky realizovat. Alternativně: minimalizace a kanonizace. 2 IB102 Automaty a gramatiky, 20. 10. 2008 22 Věta 2.76 Problém, zda L(M) je konečný, resp. nekonečný, je rozhodnutelný. Důkaz. L je nekonečný, právě když DFA M akceptuje alespoň jedno slovo w s vlastností n |w| < 2n, kde n = card(Q). (=) L nekonečný, pak existuje u 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 L. Platí |xz| n. Pokud |xz| 2n, celý postup opakujeme. (=) |w| n, pak M na w musí projít dvakrát stejným stavem. Proto w = xyz tak, že |y| 1 a platí xyi z L pro každé i N0 (viz důkaz lemmatu o vkládání), tedy L je nekonečný. Existenci w L takového, že n |w| < 2n, lze algoritmicky ověřit (slov je konečně mnoho,"vyzkoušíme" každé z nich). 2 IB102 Automaty a gramatiky, 20. 10. 2008 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 fgrep - 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, 20. 10. 2008 24