Regulární výrazy Definice 2.58. Množina regulárních výrazů nad abecedou Z, označovaná flE(Z), je definována induktivně takto: □ e, 0 a a pro každé a e Z jsou regulární výrazy nad Z (Tzk základní regulární výrazy). B Jsou-li E, F regulární výrazy nad Z, jsou také (E.F), (E + F) a (E*) regulární výrazy nad Z. Q Každý regulární výraz vznikne po konečném počtu aplikací kroků 1-2. IB102 Automaty, gramatiky a složitost, 6.10.2014 1/29 Každý regulární výraz E nad abecedou T. popisuje (jednoznačně určuje) jazyk L(E) nad abecedou T. podle těchto pravidel: L(0) = 0 L{ä) d= {a} pro každé a g Z L(E.F) =ŕ L(E).L(F) L(E + F) = L{E)UL{F) L( E*) =ŕ L(E)* IB102 Automaty, gramatiky a složitost, 6.10.2014 2/29 Příklady IB102 Automaty, gramatiky a složitost, 6.10.2014 3/29 Ekvivalence konečných automatů a reg. výrazů RE D FA Věta 2.43 N FA Věta 2.48 N FA s e-kroky 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 Z lze zkonstruovat konečné automaty, které rozpoznávají jazyky popsané základními regulárními výrazy tj. 0, {e} a {a} pro každé a e Z. 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. □ IB102 Automaty, gramatiky a složitost, 6.10.2014 4/29 Příklad IB102 Automaty, gramatiky a složitost, 6.10.2014 5/29 RE '-« D FA «_- Věta 2.43 N FA Věta 2.48 -N FA s e-kroky - 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, gramatiky a složitost, 6.10.2014 6/29 Regulární přechodový graf Definice 2.64. Regulární přechodový graf M je pětice (Q, Z, ô, I, F), kde ■ Q je neprázdná konečná množina stavů, ■ Z je vstupní abeceda, ■ S : Q x Q RE(T) je parciálni prechodová funkce, ■ / c Q je množina počátečních stavů, ■ F c Q je množina koncových stavů. IB102 Automaty, gramatiky a složitost, 6.10.2014 7/29 Příklad IB102 Automaty, gramatiky a složitost, 6.10.2014 8/29 Slovo w g Z* je akceptováno grafem M, právě když ■ existuje posloupnost stavů q0,..., qn, kde n > 0, q0 g /, q, m a <5(c7/_i, g;) je definováno pro každé 0 < / < n taková, že ■ w lze rozdělit na n částí w = v-\... vn tak, že ■ Vj g L(c)(<7/_-|, qi)) pro každé 0 < / < n. Slovo e je akceptováno také tehdy, je-li /nF/í. IB102 Automaty, gramatiky a složitost, 6.10.2014 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, 51, S, I, F) existuje ekvivalentní NFA M' s e-kroky. IB102 Automaty, gramatiky a složitost, 6.10.2014 Důkaz. Algoritmus konstrukce N FA M' s e-kroky. IB102 Automaty, gramatiky a složitost, 6.10.2014 11/29 Krok 1: Ke grafu M přidáme nový stav q0 a hranu q0 q pro každé q (z I. Stav q0 bude (jediným) počátečním stavem automatu M', prvky F jeho koncovými stavy. IB102 Automaty, gramatiky a složitost, 6.10.2014 12/29 Krok 2: Opakovaně realizuj kroky (a) a (b) dokud přechodový graf obsahuje alespoň jednu hranu ohodnocenou symbolem, který nepatří do Z 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 -4 q, kde E 0 Z u {e}, odstraň ji a prov následující: 0^1© - 04*© ©^© ^ (^(7^0 0^0 ^ (^(?^0 IB102 Automaty, gramatiky a složitost, 6.10.2014 Konečnost algoritmu M 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 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(M'). □ IB102 Automaty, gramatiky a složitost, 6.10.2014 14/29 Převod DFA na regulární výraz Motivace Věta 2.66. Pro každý regulární přechodový graf M = (Q, Z, ô, I, F) existuje ekvivalentní přechodový graf M' = ({x, y}, Z, S', {x}, {/}), kde S' může být definováno pouze pro dvojici (x, y). IB102 Automaty, gramatiky a složitost, 6.10.2014 15/29 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 A q pro každé g e / a r A y pro každé C 6 F. IB102 Automaty, gramatiky a složitost, 6.10.2014 16/29 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, gramatiky a složitost, 6.10.2014 17/29 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. □ Na regulární výraz lze stejně převést každý konečný automat (nejen DFA). IB102 Automaty, gramatiky a složitost, 6.10.2014 18/29 Ekvivalence konečných automatů a regulárních gramatik Věta 2.60, Věta 2.65 /-N RE Věta 2.62 D FA Věta 2.43 /-N, N FA Věta 2.48 Věta 2.66 N FA s e-kroky Reg. gramatiky 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, gramatiky a složitost, 6.10.2014 19/29 Převod regulární gramatiky na konečný automat Lemma 2.69. Ke každé regulární gramatice Q = (N, Z, P, S) existuje nedeterministický konečný automat M = (Q, Z, S, q0, F) takový, že L(G) = L(M). Důkaz. IB102 Automaty, gramatiky a složitost, 6.10.2014 20/29 Konstrukce konečného automatu M = (Q, Z, ô, q0, F) ■ Q = {Ä I A g N} u {qrř}, kde qrř 0 A/ ■ q0 =Š ■ á je nejmenší funkce Q x I 2° splňující: - pokud /A ->• afí je pravidlo v P, pak B g <5(A a) - pokud /A ->• a je pravidlo v P, kde a/e, pak qrř g S(A, a) {S, qy} pokud S {qf} jinak e je pravidlo v P IB102 Automaty, gramatiky a složitost, 6.10.2014 21/29 Korektnost Nejprve indukcí vzhledem ke k dokážeme, že pro každé a-i,..., ak g T. a B g N platí: S=>* a^... akB B g S(Š, aA... ak) ■ Základní krok k = 0: Z definice <5 plyne <5(S, e) = {S} a proto: S^*e B = S <=^ B = Š <=^ BeS(Š,e) ■ Indukční krok: S =>* a-i... a^+i B * a-i... S/^C a-i... a^+i fí 3C g A/ takové, že C g <5(S, ai... ak) a C a^+i S 3C g A/ takové, že Č g á (Š, a^...ak) a Š g <5(Č, afc+1) Bg 5(5,3! ...afc+1). IB102 Automaty, gramatiky a složitost, 6.10.2014 22/29 Dokázali jsme: S^*a1...a/Cfí - Š g F <í=>- e g L(.M) ■ w = va, kde ľ e P, a é I: va g /.(£) S vB^ va S^* vB A B^aeP <í=>- fl g S(Š, v) A qrř g <5(fl, a) gř g ô(S, va) • a pravidlo v P - pokud p g c>(<7o, a), je S ->• ap pravidlo v P - pokud p g c>(<7o, a) a p g F, je S ->• a pravidlo v P - pokud cfo g F, je S ->• e pravidlo v P Gramatika Q = (N, Z, P, S) je zřejmě regulární. Platí: S(q0, ^...a^nF/l, kde /c > 0, a-i,..., ak g Z * a-i... a/r IB102 Automaty, gramatiky a složitost, 6.10.2014 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 Z ■ ekvivalence: jsou M a M' ekvivalentní? (platí L(M)=L(M') ?) ■ inkluze (jazyků): platí L{M) c L(M')1 m příslušnost (slova k jazyku): je-li dáno w g Z*, platí w g L(M)7 m prázdnost (jazyka): je L(M) = 0? ■ univerzalita (jazyka): je L(M) = Z*? ■ konečnost (jazyka): je L(M) konečný jazyk? IB102 Automaty, gramatiky a složitost, 6.10.2014 26/29 Věta 2.74 Problém prázdnosti (L(M) = 0) a problém univerzality (L(M) = Z*) 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) = Z* <=^> co-L{M) = 0. □ Věta 2.77 Problém ekvivalence je rozhodnutelný pro regulární jazyky. Důkaz. Pro libovolné L|, L2 platí: (Li=L2) (L-, n co-L2) U (co-L| n L2) = 0. Pro L-i, L2 zadané automaty lze uvedené operace algoritmicky realizovat. Alternativně: minimalizace a kanonizace. □ IB102 Automaty, gramatiky a složitost, 6.10.2014 27/29 Věta 2.76 Problém, zda jazyk L zadaný automatem M je konečný, resp. nekonečný, je rozhodnutelný. Důkaz. Nechť M je DFA. L je nekonečný právě když M akceptuje alespoň jedno slovo wěPs vlastností n < \ w\ < 2n, kde n = card(Q). (=>) Je-li L nekonečný, pak existuje u g L takové, že \u\ > n. Je-li \u\ < 2/i, jsme hotovi. Nechť \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. ( n, pak M při čtení 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é / g N0 (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, gramatiky a složitost, 6.10.2014 28/29 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, gramatiky a složitost, 6.10.2014 29/29