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, gramatiky a složitost, 14.10.2013 1 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, gramatiky a složitost, 14.10.2013 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, gramatiky a složitost, 14.10.2013 3 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, 14.10.2013 4 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, gramatiky a složitost, 14.10.2013 5 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, gramatiky a složitost, 14.10.2013 6 Převod regulární gramatiky na konečný automat Lemma 2.69. Ke každé regulární gramatice Q = (iV, S, P, 5) existuje nedeterministický konečný automat Ai = (Q,S,5, qo,F) takový, že L{G) = L(M). Důkaz. IB102 Automaty, gramatiky a složitost, 14.10.2013 7 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, gramatiky a složitost, 14.10.2013 8 Korektnost Nejprve indukcí vzhledem ke k dokážeme, že pro každé oi,...,Ofe G S a B GiV platí S cti... akB < > -B G 5(5, (2i... CLk)- • Základní krok k — 0: Z definice 5 plyne ô(S,e) = {5}. Proto $ S <^=^ B — S B — S B G 5(5, s) • Indukční krok: $ (2i . . . CLk-\-lB 3(7 G iV takové, že S =^>* ai... akC => ai... ak+iB <=^> 3C e N takové, že C e 5(5, aľ.. ,ak) A C -> ak+1B 3C e N takové, že C G 5(5, ai... ak) A B G 5(ľľ, ak+i) -B G 5(5, cti... ak+i). IB102 Automaty, gramatiky a složitost, 14.10.2013 9 Dokázali jsme: 5 ai... a&P <^> B G 5(S, a\... ak) Ukážeme, že w G L(G) w G L(VW): w = e\ eeL(g) <í=> S^čGP 4=^ S G F 4=^ í G L(Ai) íi; = m, kde i; G S*ř a G S: i;a G L{Q) S =>* vB => í;a S ^* vB A B ^ a e P B G A g/ G č(B,a) qf m G L(X) IB102 Automaty, gramatiky a složitost, 14.10.2013 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) = £(£/). Důkaz. IB102 Automaty, gramatiky a složitost, 14.10.2013 11 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 q —> 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 S —> 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) Hf ^ 0, kde fc > 0, ai,..., a& G £ < > S (2l . . . CLk q IB102 Automaty, gramatiky a složitost, 14.10. 2013 12 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, gramatiky a složitost, 14.10. 2013 13 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, gramatiky a složitost, 14.10.2013 14 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, gramatiky a složitost, 14.10.2013 15 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, 14.10.2013 16 Bezkontextové jazyky Bezkontextová gramatika (context-free grammar, CFG) Q je čtveřice (iV, E, P, S), kde • N je neprázdná konečná množina neterminálních symbolů, • S je konečná množina terminálních symbolů taková, že N n S = 0 (značení: y = JVUE), • S G N je počáteční neterminál, • P C iV x y* je konečná množina pravidel. Jazyk je bezkontextový, pokud je generovaný nějakou bezkontextovou gramatikou. IB102 Automaty, gramatiky a složitost, 14.10.2013 17 Příklad g = ({E,T, F], {+,*,(,),i}, P,E), kde P obsahuje pravidla E T F E + T T * F (E) | T F IB102 Automaty, gramatiky a složitost, 14.10.2013 18 Derivační stromy pro bezkontextové gramatiky Definice 3.1. Necht Q = (N, E, P, S) je CFG. Strom T nazveme derivačním stromem v Q právě když 1. kořen má návěští S, vnitřní uzly mají návěští z N, listy mají návěští z iVUSU{e}ř 2. má-li vnitřní uzel návěští A a jeho všichni synové ni,... mají v uspořádání zleva doprava návěští X\,..., G V, pak A^X1...XkeP1 3. každý list s návěštím e je jediným synem svého otce. Výsledkem derivačního stromu T nazveme slovo vzniklé zřetězením návěští listů v uspořádání zleva doprava. IB102 Automaty, gramatiky a složitost, 14.10.2013 19 Vztah mezi derivačními stromy a relací =^> Věta 3.3. Necht Q = (iV, E, P, S) je CFG. Pak pro libovolné a £ (N U S)* platí S =^>* a právě když v Q existuje derivační strom s výsledkem a. Důkaz. Označme Q a — (iV, E, P, A), kde A e N. Dokážeme, že pro každé A e N platí A =^>* a v Q a existuje derivační strom s výsledkem a (^=) Necht a je výsledkem derivačního stromu, který má k vnitřích uzlů. Indukcí vzhledem ke k ukážeme, že pak A =^>* a. Základní krok k — 1: IB102 Automaty, gramatiky a složitost, 14.10.2013 20 Indukční krok k > 1: (IP) Tvrzení platí pro stromy s nejvýše k — Strom T s k uzly: 1 vnitřními uzly. • je-li Xi list, označme olí = Xi • není-li Xi list, pak olí je výsledkem podstromu Ti s kořenem Xi • Výsledek T je Platí: =^>* (Pro Xi, které není listem, podle (IP)) A —> X\... Xn G P (z definice deriv. stromu) Dostáváme A => X±... Xn =^>* IB102 Automaty, gramatiky a složitost, 14.10.2013 21 (=>) Necht A =^>* a. Ukážeme, že v Qa existuje derivační strom s výsledkem a. Použijeme indukci k délce odvození A =^>* a. Základní krok A 4> a: Pak a = A a odpovídající derivační strom má jen jeden uzel (kořen je list) s označením A. Indukční krok A =>* a, k > 0: (IP) Pro každé B e N platí: pokud B =^>* /3 v nejvýše fc krocích, pak v C/^ existuje derivační strom s výsledkem /3. k-\-l k ► A X\... Xn =>► QL\... ani kde ^> Konstrukce stromu s výsledkem a: □ IB102 Automaty, gramatiky a složitost, 14.10.2013 22 Jednoznačnost derivačních stromů Derivace je sekvence S =^> a± =^> =>> ... =>> an. Levá (resp. pravá) derivace je taková derivace, kde každé qlí+i vznikne z přepsáním nejlevějšího (resp. nej pravějšího) neterminálu. Každému derivačnímu stromu odpovídá jediná levá derivace. Každé levé derivaci odpovídá jediný derivační strom. Analogicky pro pravou derivaci. Existuje pro každé w £ L{Q) právě jeden derivační strom? IB102 Automaty, gramatiky a složitost, 14.10.2013 23 Definice 3.7. CFG Q se nazývá víceznačná (nejednoznačná) právě když existuje w G L{Q) mající alespoň dva různé derivační stromy. V opačném případě říkáme, že Q je jednoznačná. Bezkontextový jazyk L se nazývá vnitřně (inherentně) víceznačný, právě když každá bezkontextová gramatika, která jej generuje, je víceznačná. IB102 Automaty, gramatiky a složitost, 14.10.2013 24