Vlastnosti bezkontextových jazyků Věta 3.58. (a 3.61.) Třída bezkontextových jazyků (£2) je uzavřena vzhledem k operacím 1. sjednocení 2. zřetězení 3. iterace 4. pozitivní iterace 5. průnik s regulárním jazykem Věta 3.60. Třída bezkontextových jazyků (£2) není uzavřena vzhledem k operacím 1. průnik 2. doplněk IB102 Automaty, gramatiky a složitost, 18.11.2013 1 Sjednocení Li je generován CFG Q\ = (iVi, Si, Pi, 5i) a L2 je generován CFG Q2 = (iV2, £2, P2, S2) Bez újmy na obecnosti můžeme předpokládat N\ n iV2 = 0. Definujeme £ = (Nľ U iV2 U {S'}, Ex U E2, P, 5), kde £ je nový symbol a p = px u P2 U {5 5^1, S -> S2} Každá derivace v Q začne použitím bud S —> S\ nebo S S2. Podmínka N1nN2 = ® zaručí, že při použití S -> Sľ (resp. S S2) lze v dalším derivování používat jen pravidla z P\ (resp. P2). Jazyk L = Li U L2 je generován gramatikou Q. IB102 Automaty, gramatiky a složitost, 18.11.2013 2 Zřetězení Li je generován CFG Q\ = (iVi, Si, Pi, S\) a L2 je generován CFG Q2 = (^2, S2, P2, S2) Bez újmy na obecnosti můžeme předpokládat N\ n N2 Definujeme g = (NľUN2U {S}, £1 U E2, ^ 5), kde S je je nový symbol a P = PiUP2U{5^ 6162} Jazyk L = L\.L2 je generován gramatikou Q. IB102 Automaty, gramatiky a složitost, 18.11.2013 Iterace a pozitivní iterace Li je generován CFG Q\ = (iVi, Si, Pi, Si) Definujeme Q = (iVi U {5}, Ei, P, 5), kde 5 je je nový symbol a P = PľU{S ^ SSľ I e} Jazyk L = L* je generován gramatikou Q. Definujeme Q = (iVi U Ei, P, 5), kde 5 je je nový symbol a p = P1 u {S ^SSľ I #1} Jazyk L = je generován gramatikou Q IB102 Automaty, gramatiky a složitost, 18.11.2013 Korektnost konstrukce pro iteraci Dokážeme L{Q) = L\. IB102 Automaty, gramatiky a složitost, 18.11.2013 5 Průnik a doplněk Li = {anbncm | m,rc > 1} L2 = {am6ncm | m,rc > 1} Oba tyto jazyky jsou CFL. Kbyby C2 byla uzavřena vzhledem k operaci průniku, pak i L\ n L2 {anbncn | n > 1} musel být bezkontextový, což však není. Neuzavřenost C2 vůči doplňku plyne z její uzavřenosti na sjednocení, neuzavřenosti na průnik a z De Morgánových pravidel: Li n L2 = co-(co-Li U co-L2), tj., kdyby C2 byla uzavřena na doplněk, musela by být uzavřena i na průnik, což však není. IB102 Automaty, gramatiky a složitost, 18.11.2013 6 Průnik s regulárním jazykem L = L(V), kde V je PDA V = (Qi, E,T,5uqu Z0,F±) R = L (Ä), kde A je deterministický FA A = (Q2, E, 62, q2, F2) Sestrojíme PDA V takový, že L(P')=L n i?. "P' = (Q, E, T, 6, q0, Z0, F), kde • Q = Qi x Q2 • qo = («71,92) • F = Fi x F2 • ô : pro každé p £ Qi, q £ Q2, a £ T,U {e}, Z G T platí: ô{{p,q),a,Z) = {({p', q')n) I (p',7) € p, pak existuje rozdělení z = uvwxy splňující ra/ea uvlwxly G L(Q) pro všechna i > 0. Tedy jazyk L{Q) obsahuje nekonečně mnoho slov tvaru uvlwxly, je tedy nekonečný. IB102 Automaty, gramatiky a složitost, 18.11.2013 9 (=>) Necht L (Q) je nekonečný. Pak obsahuje i nekonečně mnoho slov délky větší než p - tuto množinu slov označme M. Zvolme z M libovolné takové slovo z, které má minimální délku a ukažme, že musí platit p < \z\ < p + q. Kdyby \z\ > p + q, pak (opět dle Pumping lemmatu pro CFL) lze z psát ve tvaru z = uvwxy, kde vx ^ e. pro všechna i > 0. vwx p + q a \vwx\ < q plyne, že \uwy > (p + q) — q = p. Tedy uwy G M, což je spor s volbou z jako slova z M s minimální délkou. Celkem tedy musí být \z < p + q. □ IB102 Automaty, gramatiky a složitost, 18.11.2013 10 Vlastnost sebevložení Definice 3.70. Necht Q = (iV,S,P,5) je CFG. Řekneme, že Q má vlastnost sebevložení, jestliže existují A £ N a u, v £ S+ taková, že A ^+ iM?;. CFL L má vlastnost sebevložení, jestliže každá bezkontextová gramatika, která jej generuje, má vlastnost sebevložení. Věta 3.71. CFL L má vlastnost sebevložení, právě když L není regulární. Důkaz ve skriptech obsahuje závažnou chybu. Kdo mi jako první pošle mail s popisem chyby, získá 1 tvrdý bod. Deadline: 30.11.2013 IB102 Automaty, gramatiky a složitost, 18.11.2013 11 Nerozhodnutelné problémy pro bezkontextové jazyky Problém regularity Neexistuje algoritmus, který pro libovolnou danou CFG Q rozhoduje, zda L{Q) je regulární či nikoliv. (Tedy není rozhodnutelné, zda L{Q) má vlastnost sebevložení či nikoliv.) Problém univerzality Neexistuje algoritmus, který pro libovolnou danou CFG Q rozhoduje, zda L(Q) = S* či nikoliv. Problémy ekvivalence a inkluze také nejsou rozhodnutelné (plyne z nerozhodnutelnosti problému univerzality). IB102 Automaty, gramatiky a složitost, 18.11.2013 12 Deterministické zásobníkové automaty Definice 3.72. Řekneme, že PDA M = (Q, E, I\ 5, Z0,F) je deterministický (DPDA), jestliže jsou splněny tyto podmínky: 1. pro všechna q £ Q a Z £ T platí: kdykoliv 5(q,e,Z) ^ 0, pak a, Z) = 0 pro všechna a £ E; 2. pro žádné g £ Q,Z £ T a a G EU {e} neobsahuje 5(q,a,Z) více než jeden prvek. Řekneme, že L je deterministický bezkontextový jazyk (DCFL), právě když existuje DPDA Ai takový, že L = L(A4). IB102 Automaty, gramatiky a složitost, 18.11.2013 13 Vlastnosti deterministických bezkontextových jazyků Věta 3.82. Třída DCFL je uzavřena na doplněk. Intuice: DPDA má nad každým slovem právě jeden výpočet. Pro doplněk stačí zaměnit koncové a nekoncové stavy. Komplikace 1: DPDA nemusí dočíst vstupní slovo do konce, protože se vyprázdní zásobník nebo přechod není definován. Řešení: IB102 Automaty, gramatiky a složitost, 18.11.2013 14 Komplikace 2: DPDA nemusí dočíst vstupní slovo do konce, protože přestane číst vstup a neustále provádí e-kroky pod kterýmy zásobník neomezeně roste. Řešení: s = \Q\ t = |T| r = max{|7| | (p',7) 1} a L2 = {ambncrn \ m,n > 1} jsou DCFL, ale L\ n L2 = {an6ncn | n > 1} není ani bez kontextový. □ Věta. Třída DCFL je uzavřena na průnik s regulárním jazykem. Věta. Třída DCFL není uzavřena na sjednocení. Důkaz. Plyne z uzavřenosti na doplněk, neuzavřenosti na průnik a z De Morgánových pravidel: L\ n Z/2 = co-(co-Z/i U co-Z/2) (Z uzavřenosti na sjednocení by plynula uzavřenost na průnik.) □ IB102 Automaty, gramatiky a složitost, 18.11.2013 18 Vztah deterministických a nedeterministických CFL Věta. Třída DCFL tvoří vlastní podtřídu třídy bezkontextových jazyků Zejména existují bezkontextové jazyky, které nejsou DCFL. Příklad. Jazyk co-{ww | w £ {a, 6}*} je CFL, ale není DCFL IB102 Automaty, gramatiky a složitost, 18.11.2013 19 Aplikace (deterministických) bezkontextových jazyků • syntaxe programovacích jazyků je definována pomocí CFG (dobře uzávorkované výrazy, //- then - else konstrukty) • DTD (Document Type definition) umožňuje definovat bezkontexové jazyky - využití ve značkovacích jazycích (HTML, XML,. . . ) • nástroje pro tvorbu parserů/překladačů využívají různé algoritmy pro lineární deterministickou syntaktickou analýzu: LALR(l) - Yacc, Bison, javacup LL(k) - JavaCC, ANTLR IB102 Automaty, gramatiky a složitost, 18.11.2013 20 Turingův stroj - syntaxe Definice. (Deterministický) Turingův stroj (Turing Machine, TM) je devítice M = (Q, £, I\ >, U, ô, q0, gacc, qľe]), kde • Q je konečná množina, jejíž prvky nazýváme stavy, • S je konečná množina, tzv. vstupní abeceda, • T je konečná množina, tzv. pracovní abeceda, S C T, • > G T \ S je levá koncová značka, • U G T \ S je symbol označující prázdné políčko, • ô : (Q \ {gacc, qrej}) x T Q x T x {L, R} je totální přechodová funkce, • ?o G Q je počáteční stav, • ?acc G Q je akceptující stav, • ?rej G Q je zamítající stav. IB102 Automaty, gramatiky a složitost, 18.11.2013 21 Dále požadujeme, aby pro každé q £ Q existoval p G Q takový, že ô(q,>) = (p, >,i2) (tj. > nelze přepsat ani posunout hlavu za okraj pásky). Označení. UW = UUUUUU... Definice. Konfigurace Turingova stroje je trojice (g, z, n) &Qx{yUUJ y G T*} x N0, kde • q je stav, • y\Ju je obsah pásky, • n značí pozici hlavy na pásce. Počáteční konfigurace pro vstup w £ S* je trojice (qo, >wUu;,0). Akceptující konfigurace je každá trojice tvaru (#acc>2, n). Zamítající konfigurace je každá trojice tvaru (qTe^z,ri). IB102 Automaty, gramatiky a složitost, 18.11.2013 22 Výpočet Turingova stroje Označení. Pro libovolný nekonečný řetěz z nad I\ zn označuje n-tý symbol řetězu z (z$]e nejlevější symbol řetězu z). Dále s%(z) označuje řetěz vzniklý ze z nahrazením zn symbolem b. Definice. Na množině všech konfigurací stroje Ai definujeme binárni relaci m (krok výpočtu) takto: {p, z, n) m {q, s%(z),n + 1) pro ô(p, zn) = (q, b, R) {q, s%(z),n - 1) pro 5{p, zn) = {q, b, L) IB102 Automaty, gramatiky a složitost, 18.11.2013 23 Výpočet TM Ai na vstupu w je maximálni (konečná nebo nekonečná) posloupnost konfigurací K0, Äi, ..kde K0 je počáteční konfigurace pro w 3 Kí \-tj-Kí+i pro všechna i > 0. Stroj A4 akceptuje slovo w právě když výpočet A4 na w je konečný a jeho poslední konfigurace je akceptující. Stroj .M zamítá slovo u> právě když výpočet A4 na u> je konečný a jeho poslední konfigurace je zamítající. Stroj A4 pro vstup w cyklí právě když výpočet A4 na u> je nekonečný. Jazyk akceptovaný TM definujeme jako L (M) = {w eY,* \ M akceptuje w}. IB102 Automaty, gramatiky a složitost, 18.11.2013 24 Ukázky Turingových strojů Simulátor TM: http://www.fi.muni.cz/~xbarnat/tafj/turing/ Různé úrovně popisu TM • formální • neformální implementační • vysokoúrovňový IB102 Automaty, gramatiky a složitost, 18.11.2013 25 Vícepáskový Turingův stroj Definice, ^-páskový Turingův stroj je definován stejně jako TM s výjimkou přechodové funkce 5, která je definována jako totální funkce 5: (Q\ Kec, ftej}) xTfc -> Q x Tk x {L, fl}*. Konfigurace majítvar ... ... ,n^) G Qx(^.{U^I^xNq. Počáteční konfigurace pro w e S* je (g0, >w\Ju, >UU,..., >Ua;, 0,____ Definice akceptující/zamítající konfigurace a |-^- se změní podobně. IB102 Automaty, gramatiky a složitost, 18.11.2013 26 Ekvivalence vícepáskového a jednopáskového TM Věta. Pro každý vícepáskový Turingův stroj existuje ekvivalentní (jed n o páskový) TM. Důkaz. 1. Neprázdný obsah k pásek a polohy hlav zapíšeme za sebe na 1 pásku. 2. Simulaca jednoho kroku = zjistit informace pod hlavami, zapsat nové a posunout hlavy. 3. Je-li třeba další políčko nějaké pásky, posuneme zbývající obsah. □ IB102 Automaty, gramatiky a složitost, 18.11.2013 27 Nedeterministický Turingův stroj Definice. Nedeterministický Turingův stroj Á4 je definován stejně jako TM s výjimkou přechodové funkce 5, která je definována jako totální funkce 5 : (Q \ {gacc, grej}) x T -> 2^xFx^L^. Všechny pojmy se definují stejně jako u deterministického TM. Drobné změny jsou jen u definice kroku výpočtu a akceptace slova. ip^.n) (q,s%(z),n+ 1) jestliže (q,b,R) e S(p,zn) (p,z,n) (q>sb(z)>n~ !) Jestliže {q,L) e $(Pizn) Ai akceptuje slovo w, právě když existuje výpočet z počáteční konfigurace pro w do nějaké akceptující konfigurace. IB102 Automaty, gramatiky a složitost, 18.11.2013 28 Ekvivalence nedeterministického a deterministického TM Věta. Pro každý nedeterministický Turingův stroj Aí existuje ekvivalentní deterministický TM. Intuice: IB102 Automaty, gramatiky a složitost, 18.11.2013 29 Důkaz. Sestrojíme 3-páskový deterministický TM prozkoumávající výpočtový strom stroje J\í. Tento 3-páskový stroj lze převést na jednopáskový deterministický TM. Necht k = max{|5(g, z)\ \ q G Q \ {qacc, qľe]},z G T}. 1. páska obsahuje vždy pouze vstup, nemění se. 2. páska slouží k simulaci nedeterministického stroje. 3. páska obsahuje řetězec určující, který uzel stromu je právě prohledáván. IB102 Automaty, gramatiky a složitost, 18.11.2013 30 Hledáme akceptující konfiguraci ve výpočtovém stromě prohledáním do šírky. Kontrola jednoho uzlu výpočtového stromu: 1. Zkopíruj první pásku na druhou. 2. Na 2. pásce simuluj Af, nedeterministické volby řeš podle čísel na 3. pásce. Narazíš-li na akceptující stav, akceptuj. V ostatních případech (příslušná volba neexistuje nebo M dojde do zamítajícího stavu nebo došly čísla na 3. pásce) pokud pokračuj dalším krokem. 3. Náhrad obsah řetězce na 3. pásce jeho následníkem v lexikografickém uspořádání a začni znovu. □ IB102 Automaty, gramatiky a složitost, 18.11.2013 31 Další varianty Turingova stroje • Turingův stroj s oddělenou vstupní páskou • Turingův stroj s oboustranně nekonečnou páskou • Stroj se dvěma zásobníky • Stroj se vstupní páskou a dvěma počítadly • . . . Všechny tyto varianty mají tutéž vyjadřovací sílu. IB102 Automaty, gramatiky a složitost, 18.11. 2013 32 Churchova teze Churchova (Church-Turingova) teze: Každý proces, který intuitivně nazvat algoritmem, se dá realizovat na Turingově stroji. Další ekvivalentní formalismy: • Minského stroje • A-kalkul • while-programy IB102 Automaty, gramatiky a složitost, 18.11.2013 Turingovy stroje a třídy jazyků Věta. Jazyk L je rekursivně spočetný (tj. generovaný gramatikou typu 0) L je akceptovaný nějakým Turingovým strojem. Definice. Turingův stroj se vstupní abecedou S se nazývá úplný, je-li každý jeho výpočet konečný (akceptující nebo zamítající). Jazyk se nazývá rekursivní, pokud je akceptovaný nějakým úplným Turingovým strojem. IB102 Automaty, gramatiky a složitost, 18.11.2013 34 Přehled jazykových tříd Jazyky Gramatiky (typ) Automaty rekursivně spočetné rekursivní kontextové bezkontextové deterministické CFL regulární frázové (0) kontextové (1) bezkontextové (2) regulární (3) Turingovy stroje úplné Turingovy stroje lineárně ohraničené TM zásobníkové automaty deterministické PDA konečné automaty Třída na nižším řádku je vždy vlastní podtřídou třídy na vyšším řádku. IB102 Automaty, gramatiky a složitost, 18.11.2013 35 Problémy jako jazyky Problém rozhodnout, zda dané w má vlastnost P lze ztotožnit s množinou {w | w má vlastnost P}. Objekty w lze kódovat jako slova (w). Problém pak ztotožníme s jazykem {(w) | w má vlastnost P}. Příklad. Problém rozhodnout, zda daný konečný graf je souvislý, ztotožníme s jazykem {(G) \ G je konečný souvislý graf}. IB102 Automaty, gramatiky a složitost, 18.11.2013 36 Rozhodnutelnost problémů Definice. Problém P je • rozhodnutelný {(w) | w má vlastnost P} je rekursivní • nerozhodnutelný {(w) \ w má vlastnost P} není rekursivní • částečně rozhodnutelný (semirozhodnutelný) {(w) | w má vlastnost P} je rekursivně spočetný IB102 Automaty, gramatiky a složitost, 18.11.2013 37 Problém zastavení (Halting Problem) Problém zastavení je problém rozhodnout, zda daný TM Ai akceptuje dané slovo w nad jeho vstupní abecedou. Problém ztotožníme s jazykem {(Aí,w) | M je TM, w je slovo nad jeho vstupní abecedou a Ai akceptuje w}. Věta. Problém zastavení je částečně rozhodnutelný. Důkaz. Stačí dekódovat Ai a w a simulovat výpočet Ai na w. □ IB102 Automaty, gramatiky a složitost, 18.11.2013 38 Věta. Problém zastavení je nerozhodnutelný. Důkaz. Předpokládejme, že existuje TM T-L rozhodující problém zastavení. Tedy T-L vstupu (A4,w) akceptuje, právě když pokud Á4 akceptuje w. S využitím 7í zkonstruujeme TM V\ dostane-li V na vstupu zakódovaný stroj (M), zeptá se stroje T~L} zda M akceptuje svůj vlastní kód {M) a následně odpověd otočí. Tedy V akceptuje (M), pokud M neakceptuje (M) a V neakceptuje (M), pokud M akceptuje {M). Nyní spustíme V na vstupu (V): V akceptuje (V), pokud V neakceptuje (V) a V neakceptuje (V), pokud V akceptuje (V). To je spor. Stroj 7í tedy neexistuje a problém zastavení je nerozhodnutelný. □ IB102 Automaty, gramatiky a složitost, 18.11.2013 39