Slezská univerzita v Opavě fllozoficko-přírodovědecká fakulta ústav informatiky Teorie jazyků a automatů II Studijní opora Poslední změny: 26. února 2008 ■v RNDr. Šárka Vavrečková sarka.vavreckova@fpf.slu.cz http://fpf.slu.cz/~vavlOui Opava 2008 Obsah Úvod 1 1 Vlastnosti bezkontextových jazyků 3 1.1 Kritéria bezkontextovosti ......................... 3 1.1.1 Pumping lemma pro bezkontextové jazyky........... 3 1.1.2 Parikhův vektor........................... 9 1.1.3 Dyckův jazyk............................ 12 1.2 Jak poznat zda je jazyk bezkontextový.................. 14 1.3 Uzáverové vlastnosti bezkontextových jazyků............. 15 1.3.1 Regulární operace ......................... 15 1.3.2 Operace, vzhledem k nimž je ještě třída Jr(CF) uzavřena . . 16 1.3.3 Operace, vzhledem k nimž třída Jr(CF) není uzavřena . ... 18 1.4 Uzáverové vlastnosti jako kritérium bezkontextovosti......... 19 2 Zásobníkový automat 21 2.1 Definice zásobníkového automatu.................... 21 2.2 Vztah mezi různými typy zásobníkových automatů.......... 25 2.3 Vztah zásobníkových automatů a bezkontextových jazyků...... 28 2.4 Zásobníkové automaty a uzáverové vlastnosti bezkontextových jazyků 35 2.5 Deterministické bezkontextové jazyky.................. 37 2.5.1 Deterministický zásobníkový automat.............. 37 2.5.2 Uzáverové vlastnosti deterministických bezkontextových jazyků ................................. 38 ii 3 Jazyky typu O 40 3.1 Gramatiky typu O.............................. 40 3.2 Stroje rozpoznávající jazyky typu O.................... 42 3.2.1 Zásobníkový automat se dvěma zásobníky........... 42 3.2.2 Turingův stroj............................ 44 3.2.3 Varianty Turingova stroje..................... 48 3.3 Vztah Turingových strojů k jazykům typu 0............... 49 4 Jazyky typu 1 56 4.1 Gramatiky typu 1.............................. 56 4.2 Kurodova normální forma pro gramatiky typu 1............ 58 4.3 Lineárně ohraničený automat....................... 60 4.4 Uzáverové vlastnosti jazyků typu 1.................... 63 5 L-systémy 65 5.1 Paralelní odvozování............................ 65 5.2 OL-systémy.................................. 66 5.3 EOL-systémy................................. 69 5.4 TOL-systémy................................. 72 5.5 ETOL-systémy................................ 74 5.6 Možnosti využití L-systémů v grafice .................. 75 6 Formální systémy 77 6.1 Derivace v gramatikách .......................... 77 6.2 Gramatiky používající řízenou sekvenční derivaci........... 78 6.3 Gramatické systémy ............................ 79 6.3.1 Kolonie................................ 80 Seznam použitých jazyků 86 Seznam definic 0.1 Definovaný pojem............................. 1 1.1 Parikhův vektor slova........................... 8 1.2 Parikhův vektor jazyka .......................... 9 1.3 Lineární podmnožina množiny Nn.................... 9 1.4 Semilineární množina........................... 10 1.5 Dyckův jazyk................................ 12 2.1 Zásobníkový automat........................... 22 2.2 Konfigurace zásobníkového automatu.................. 22 2.3 Přechod mezi konfiguracemi....................... 22 2.4 Základní typy zásobníkových automatů................. 23 2.5 Deterministický ZA ............................ 37 2.6 Deterministický bezkontextový jazyk.................. 37 3.1 Gramatika typu 0.............................. 40 3.2 Kurodova normální forma pro gramatiky typu 0............ 40 3.3 Zásobníkový automat se dvěma zásobníky............... 43 3.4 Konfigurace a přechod mezi konfiguracemi............... 43 3.5 Turingův stroj................................ 44 3.6 Konfigurace Turingova stroje....................... 45 3.7 Relace přechodu mezi konfiguracemi.................. 46 3.8 Rekurzívně spočetný jazyk........................ 49 3.9 Rekurzívní jazyk.............................. 49 4.1 Nezkracující gramatika .......................... 56 4.2 Kontextová gramatika........................... 56 4.3 Kurodova normální forma pro gramatiky typu 1............ 58 iii iv 4.4 Lineárně ohraničený automat....................... 60 4.5 Konfigurace lineárně ohraničeného automatu ............. 60 5.1 OL-schéma.................................. 66 5.2 OL-systém.................................. 67 5.3 Jazyk OL-systému.............................. 67 5.4 EOL-schéma................................. 70 5.5 EOL-systém................................. 70 5.6 Jazyk EOL-systému............................. 70 5.7 TOL-schéma................................. 72 5.8 TOL-systém................................. 72 5.9 Jazyk TOL-systému............................. 72 6.1 Maticová gramatika............................ 78 6.2 Kolonie.................................... 81 Úvod Tento studijní text je určen pro studenty kurzu Teorie jazyků a automatů II a navazuje na obdobný studijní text pro předchozí kurz Teorie jazyků a automatů I. Předpokládají se znalosti v rozsahu předchozího kurzu, především z oblasti bezkontextových a regulárních gramatik. Samotný výklad sestává zejména z definic, vět a důkazů, ovšem většinou nejde o důkazy v pravém smyslu slova, jsou hodně zjednodušené. „Opravdový" důkaz není jen popis konstrukce, ale musí být dokázáno, že tato konstrukce je správná. Text je hojně doprovázen příklady, které mají zvýšit názornost výkladu. V textu jsou graficky vyznačeny některé části: Příklad 0.1 - Takto jsou vyznačeny příklady. Jsou číslovány v závislosti na čísle kapitoly a je na ně v textu odkazováno pomocí tohoto číslování. Definice 0.1 (Definovaný pojem) Takto je vyznačena definice jednoho nebo více pojmů. Definice jsou číslovány v závislosti na čísle kapitoly. Veta 0.1 Takto jsou vyznačeny vety, opět jsou číslovány. Kapitola 1 ještě nebyla, proto zde máme jako číslo kapitoly 0. Lemma 0.2 Lemmata (pomocné věty) jsou vyznačena podobně jako věty, číslování je simultánní s větami. Lemma obvykle obsahuje tvrzení, které je pak použito v důkazu „větší" věty. 1 Úvod 2 Důkaz: Takto vyznačujeme důkaz věty nebo lemmatu. Každá věta by měla být dokázána, zde však, stejně jako v předchozím studijním textu pro kurz Teorie jazyků a automatů I, jsou pod pojmem důkaz obvykle míněny spíše konstrukce naznačující důkaz nebo vztah. Důkazy končí symbolem prázdného čtverečku. □ Myšlenka důkazu: Myšlenka důkazu naznačuje, jak by mohl být vytvořen důkaz. Narozdíl od důkazu samotného nekončí symbolem čtverečku. Důsledek 0.3 Takto je vyznačen důsledek předchozích vět. Obvykle je také uvedeno, ze kterých vět tento důsledek vyplývá, a nebo následuje důkaz stejně jako za kteroukoliv větou. Poznámka: Takto je vyznačena poznámka, ve které je obvykle okomentován důkaz, věta nebo definice. p, můžeme rozložit na pět částí w = x-y ■ z-u-v, přičemž • \y ■ u\ > 0 (v alespoň jedné z těchto dvou částí musí být alespoň jeden symbol), • \yzu\ < q (prostřední část má omezenou délku), • x-y% ■ z-u1 -v G L pro každé i > 0 (po iteraci těchto dvou částí slovo zůstává v jazyce). Nejdřív si větu rozebereme a potom teprve uvedeme důkaz. Kapitola 1 Vlastnosti bezkontextových jazyků 4 x y z u v (a) Odvození slova xyzuv (b) Odvození slova xy2zu2v Obrázek 1.1: Nákres použití Pumping lemma Myšlenka důkazu: Podíváme se na obrázek 1.1. Věta se zakládá na této úvaze: 1. Když je jazyk bezkontextový, pak pro něj musí existovat bezkontextová gramatika. 2. V této gramatice musí pro každé slovo jazyka existovat derivace. 3. Označme n = \N\ počet neterminálů gramatiky a d délku nejdelšího pravidla gramatiky, d max \a (A —► a) G P) pro nějaké A G Nj. Pak v každém kroku derivace se slovo prodlouží nejvýše o d znaků, a tedy po n krocích odvození n ■ d se prodlouží maximálně o n ■ d znaků. 4. Derivace slov delších než n ■ d znaků musí být proto delší než n. 5. Když je derivace delší než n, tak to znamená, že alespoň jeden neterminál musel být v průběhu derivace přepisován více než jednou (podle obrázku 1.1a je to neterminál A). 6. Když rozdělíme dostatečně dlouhé slovo w G L podle obrázku 1.1a na pět částí w = x-y-z-u-v, tak vlastně zkoumáme, zda v případné derivaci existuje některý opakovaně přepisovaný neterminál. Pokud jde o bezkontextový jazyk, tak takový neterminál (cyklus) musí existovat, ale není řečeno, že ho objevíme „náhodně", okamžitě a napoprvé. 7. Když se nám takový cyklus podaří najít, pak (podle obrázku 1.1b) můžeme v této derivaci „pumpovat" - při přepsání druhého zobrazeného výskytu Kapitola 1 Vlastnosti bezkontextových jazyků 5 symbolu A prostě použijeme to pravidlo, které jsme původně použili při přepsání prvního zobrazeného výskytu symbolu A a tak pokračujeme v celém podstromě. Krajní řetězce x a v a nejvnitřnější řetězec z zůstanou takové, jaké byly, jen řetězce y au se zdvojí. Cestu mezi dvěma výskyty symbolu A jsme vlastně zdvojili, ale můžeme ji opakovat kolikrát chceme, a nebo dokonce oba výskyty symbolu A ztotožnit (pro první výskyt symbolu A použijeme to pravidlo, které jsme v původní derivaci použili pro druhý), to odpovídá hodnotě i = 0 ve větě 1.1. Ještě zbývá číslo q. Jeho úkolem je zajistit, aby délka části derivace mezi dvěma výskyty A nebyla nekonečná. Toto číslo může být stanoveno zcela náhodně (samozřejmě nikoliv nekonečno), například si můžeme stanovit, že na obrázku 1.1b v podstromě s kořenem ohodnoceným prvním výskytem A je pouze to jediné další A, třetí se tam už nevyskytuje (ale v derivaci mezi S a prvním A klidně ještě nějaké být může). Důkaz: Nechť L je bezkontextový jazyk. Pak existuje některá bezkontextová gramatika G = (N,T,P,S) taková, že L = L (G). Pro zjednodušení důkazu předpokládejme, že tato gramatika je v Chomského normální formě (tj. na pravé straně pravidla jsou buď dva neterminály nebo jeden terminál). Derivační strom gramatiky v CNF je binární (kromě přímých cest k listům). Označme n = \N\. Vezmeme si nyní některé slovo w E L takové, že v jeho derivaci je nejméně dvakrát přepisován tentýž neterminál (nazvěme ho třeba A), to znamená, že v de-rivačním stromě tohoto slova se na cestě od kořene k některému listu nachází dva uzly označené symbolem A, tyto uzly nazveme ui a u2 (ui je blíž kořeni stromu). Pokud je na této cestě více uzlů označených symbolem A než dva, zvolíme uzel ui tak, aby na cestě od ui k jakémukoliv listu v jeho podstromě byl jen jediný další uzel označený symbolem A, tj. u2. Při splnění podmínky z předchozího odstavce je cesta od ui ke kterémukoliv listu jeho podstromu dlouhá nejvýše n + 1 uzlů. Protože jde o binární strom, má podstrom uzlu u\ nejvýše 2n listů. Touto hodnotou je tedy omezena délka slova y ■ z ■ u, proto lze zvolit q = 2n. Hodnota čísla p udává, jak dlouhé musí být slovo, aby v jeho derivačním stromě existovala cesta od kořene k některému listu taková, že některé dva uzly na této Kapitola 1 Vlastnosti bezkontextových jazyků 6 cestě jsou ohodnoceny stejným neterminálem. Z předchozích odstavců důkazu je zřejmé, že všechna slova nevyhovující této podmínce mají derivační strom, v němž jsou všechny větve kratší než n (tj. dlouhé nejvýše n — 1). Takový derivační strom má tedy nejvýše 2n_1 listů (a tedy vygenerovaných terminálů). Proto položíme P in—1 □ Příklad 1.1 - V tomto příkladu si ukážeme, že bezkontextový jazyk splňuje Pumping lemma. Lx = {anbn I n > 1} Protože předem neznáme přesné hodnoty p a q z věty 1.1, budeme používat symbolicky přímo index p s předpokladem, že jde o „dostatečně velké" číslo. = ďW Zvolíme toto rozdělení: w X y z u v ď-1 a e b If-1 Pak dostáváme slova ď^áWtP-1 = ap+í_16p+í_1, což jsou pro jakékoliv číslo i > 0 slova patřící do jazyka L\. Číslo p zde lze položit například p = 2 (nebo vyšší). Tento jazyk generuje například gramatika s těmito pravidly S —► aSb \ ab Poznámka: Pumping lemma je pouze implikace (ve tvaru „jestliže je jazyk bezkontextový, pak splňuje tuto vlastnost"). Proto ji nelze použít tak, že po zjištění, že jazyk splňuje danou vlastnost, bychom tento jazyk prohlásili za bezkontextový. Například jazyk {anbn \ n > 0} • {anbncn \ n > 0} není bezkontextový, třebaže splňuje podmínky Pumping lemma. Obecně to lze říci o všech jazycích, které sice nejsou bezkontextové, ale lze je napsat jako zřetězení dvou jazyků, z nichž alespoň jeden je bezkontextový. Poznámka: Pumping lemma se obvykle používá pro důkaz, že některý jazyk není bezkontextový, tedy důkaz sporem. Větu obrátíme: A B ^B -nA (1.1) V přepisu: Jestliže jazyk je bezkontextový, pak má danou vlastnost. Kapitola 1 Vlastnosti bezkontextových jazyků 7 je totéž jako Jestliže jazyk nemá danou vlastnost, pak není bezkontextový. Příklad 1.2 - Dokážeme, že jazyk L2 = {anbncn \ n > 0} není bezkontextový. Zvolíme slovo w = ďWď pro některé dostatečně velké číslo p. Možná rozdělení tohoto slova jsou v tabulce. Musíme brát v úvahu konečnost konstanty q, v části yzu se proto nesmí vyskytovat „potenciálně nekonečný" index p. X y z u v xytzutv pro i = 0 ďvď-1 c e e e ďlfcp-1+i ďVď-1 <£ L2 ďv-1 b c e ď-i ďV^ď <£ L2 ďv-1 b e c ď-i ďlf-i+íď-i+í ďVP-iď-i ^ L<2 ďlf-2 bb e CC ď'2 aP^p-2+2í cp-2+2í ďVP-2ď-2 ^ L<2 Při splnění podmínek Pumping lemma (\yu\ > 0, \yzu\ < q) vidíme na tabulce, že „pumpující" část yu může zachytit nejvýše dva druhy symbolů (buďjen symboly a, nebo jen b, c, a nebo jen a, b, b, c), tedy přibývat (nebo ubývat pro i = 0 nemohou zároveň symboly a, b i c a proto při jakémkoliv možném rozdělení vznikají iterací slova nepatřící do jazyka L2. Proto L2 ^ =žf (CF)1. Příklad 1.3 - Dokážeme, že jazyk L3 = j a™2 n > 0 j není bezkontextový. Opět zvolíme nějaké slovo w = ap2 G L3 s „dostatečně velkým" indexem p. Toto slovo rozdělíme následovně: ap2 = aXlaX2aXzaXAaX5 a musí platit x2 + x4 > 0, x2 + x3 + x4 < q Před iterací: p2 = Xi + x2 + x3 + xA + x5 Po iteraci: m2 = Xi + i ■ x2 + x3 + i ■ xA + x5 = i ■ (x2 + X4) + (xx + x3 + Získali jsme rovnici, v jejichž obou částech oddělených rovnítkem jsou funkce. Zatímco levá část rovnice roste exponenciálně, pravá lineárně (je to lineární funkce) 1CF značí bezkontextové gramatiky, Jíf(CF) znamená třídu (tj. množinu) jazyků generovaných bezkontextovými gramatikami, tj. bezkontextové jazyky. Kapitola 1 Vlastnosti bezkontextových jazyků 8 a tedy mnohem pomaleji. Aťstanovíme indexy x2 a X4. jakkoliv, vždy se najde číslo i, pro které součet indexů není roven druhé mocnině žádného čísla. L3 ^ Jšf (CF). Příklad 1.4 - Pomocí Pumping lemma dokážeme, že jazyk L4 = j a2" n > 0 j není bezkontex-tový. Důkaz bude podobný předchozímu. Zvolíme nějaké slovo w = aT E L4 s „dostatečně velkým" indexem r. Toto slovo rozdělíme na aT = axlaX2axsaX4aX5 a musí platit x2 + xA > 0, x2 + x3 + xA < q Před iterací: 2r = xl + rr2 + ^3 + x4 + ^5 Po iteraci: 2m = + i ■ x2 + x3 + i ■ xA + x5 = i ■ (x2 + xA) + (rri + x3 + rr5) Získali jsme rovnici, v jejichž obou částech oddělených rovnítkem jsou funkce. Zatímco levá část rovnice roste exponenciálně, pravá lineárně (je to lineární funkce) a tedy mnohem pomaleji. Aťstanovíme indexy jakkoliv, vždy se najde číslo i, pro které součet indexů není roven žádné mocnině čísla 2. Proto L4 ^ Jr(CF). Příklad 1.5 - Dokážeme, že jazyk L5 = {ww \ w E {a, b}*} není bezkontextový. Tento jazyk se skládá ze slov, která mají obě poloviny stejné. Pro důkaz si vybereme slovo w = ďtřďtř, p > 4, q = 4 a dokážeme, že pro toto slovo neexistuje žádné rozdělení, které by umožňovalo „pumpování" dle Pumping lemma. X y z u v xytzutv pro i = 0 ďlf-1 b e a ď'1 V ďtíP-i+iaP-i+ibP ďbP^ď^If <£ L5 ďv-1 e b a ď'1 V aPbPaP-l+iy> ďlf-1 e e ba ď'1 V ďbP-^baYď-1^ Jak vidíme, většinou nám úplně stačí pro každé rozdělení otestovat slovo pro i = 0. Můžeme pokračovat dalšími řádky tabulky, ale vždy dojdeme ke stejnému závěru. Je to proto, že když je část yzu omezena konstantou, může zabrat nejvýše dvě různé části ze čtyř částí vybraného slova w (a přitom do yu musí padnout alespoň Kapitola 1 Vlastnosti bezkontextových jazyků 9 jeden symbol slova), tedy po iteraci pro žádné i kromě i = 1 nedostaneme slovo, jehož obě poloviny jsou stejné. Proto L5 ^ áf(CF). Poznámka: Podobně by mohl vypadat důkaz, že jazyk L6 = {anbman | 0 < m < n} není bezkontextový (kdyby v definici tohoto jazyka nebyly nerovnosti, šlo by o bez-kontextový jazyk). Tento důkaz ponecháváme na čtenáři. 1.1.2 Parikhův vektor Definice 1.1 (Parikhův vektor slova) Nechť L je některý jazyk nad abecedou E, kde E = {di, a2,..., an}, |E| = n. Parikhův vektor slova w G L je kde #clí(w) značí počet symbolů a,i ve slově w. Definice 1.2 (Parikhův vektor jazyka) Nechť L je některý jazyk nad abecedou E, kde E = {ai, a2,..., an}, |E| = n. Parikhův vektor jazyka L je množina Parikhových vektorů všech slov tohoto jazyka, tedy ifj(L) = {ifj(w) \w 1} ifj(aaabbb) = (3, 3) ^(L1) = {i-(l,l)|i>l} L7 = {(řnbn+2aAcn | n > 1} ^(a664a4c2) = (10,4,2) ij}{L7) = {(3n + 4,n + 2,n) | n > 1} = = {n-(3,l,l) + (4,2,0)|n>l} L8 = {a^V1-1 | n > 1} zde je problém konstanta (—1) v exponentu - položme k = n — 1, tedy k + 1 = n: ifj(Ls) = {(2 • (k + 1), k) I k > 0} = {k ■ (2,1) + (2,0) | k > 0} Kapitola 1 Vlastnosti bezkontextových jazyků 10 Z algebry si určitě pamatujeme operace s vektory - sčítání vektorů a násobení vektoru celým číslem: Dále budeme používat toto značení: N je množina přirozených čísel (zde včetně 0) Nn je množina všech n-prvkových vektorů nad množinou N Definice 1.3 (Lineární podmnožina množiny N") Lineární podmnožina množiny Nn pro nějaké n G N je {v0 + rii ■ vi + n2 ■ v2 + ... + nk ■ vk \ n,-, G N, 1 < i < k, v j G Nn, 0 < j < k} (rii jsou čísla, v j jsou vektory čísel) Definice 1.4 (Semilineární množina) Semilineární množina je konečné sjednocení lineárních podmnožin množiny Nn. Věta 1.2 Pro každý bezkontextový jazyk L je ip(L) semilineární množina. Důkaz této věty by byl složitý, proto ho zde nebudeme uvádět. Příklad 1.7 - L9 = {áLVck I i, j, k > 1, i = j neboj = k} Parikhův vektor jazyka Lg je jednocení „dílčích" lineárních množin, a tedy semilineární množina. Poznámka: Stejně jako Pumping lemma, i zde se jedná pouze o implikaci. Opět budeme tuto větu používat v důkazu sporem - jestliže Parikhův vektor daného jazyka není semilineární množina, pak to není bezkontextový jazyk. (x1,x2,...,xn) + (yi,y2,...,yn) (x1 + í/i, x2 + y2, ■ ■ ■, xn + yn) (1.2) (1.3) ^(L9) = {i ■ (1,1, 0) + k ■ (0,0,1) \i, k > 1} ^2(L9) = {i-(l,0,0)+j-(0,l,l) Kj>l} Íj(L9) =^1(L9)U^2(L9) Kapitola 1 Vlastnosti bezkontextových jazyků 11 Příklad 1.8 - Lio = {a*bc} U {apbanc \ n > 0,p je prvočíslo} MLio) = {* "(1,0,0) + (0,1,1) |i>0} M^io) = {n- (1,0,0) +p- (1,0,0) + (0,1,1) I n > 0, p je prvočíslo} ^(Lio) = ipi(L10) U i/j2(L10) Množina ^2(^10) není lineární, a proto množina ip(Lw) není semilineární. Neexistuje konečné sjednocení lineárních množin popisujících množinu odvozenou z prvočísel, to bychom museli postupně vyjmenovat všechna prvočísla (a to by nebylo konečné sjednocení). Proto Lí0 ^ (CF). Ln = [an%n I n > l} ijj(Lii) = {n2-(l, 0)+n-(0,1) | n > 1} není semilineární množina (je zde kvadratická funkce). Proto Ln <£ Jr(CF). Ale pozor! L12 = |an6n|l 1} ^(Li) = {n • (1,1)| n >1} R1=ab(ab)*, ^(i?i) = ^(Lx) L7 = {a3nbn+2aAcn | n > 1} ^(a664a4c2) = (10,4,2) tp(L7) = {(3n + 4, n + 2, n) | n > 1} = {n ■ (3,1,1) + (4, 2,0) | n > 1} f?7 = (aaabc)*aaabcaaaabb, ipiRj) = ip{L7) Důkaz: Označme abecedu, nad kterou je definován jazyk, E = {ai,..., ar}, tj. má celkem r prvků. Věta vyplývá z věty 1.2 na straně 10 - když je Parikhův vektor jazyka semilineární množina a tedy sjednocení lineárních množin, tak postupně Kapitola 1 Vlastnosti bezkontextových jazyků 12 všechny lineární množiny ve tvaru {v0 + rii ■ vi + n2 ■ v2 + ... + nk ■ vk \ rii E N, 1 < i < k, v j E Nn, 0 < j < k} rozložíme na jednotlivé vekory násobené číslem rii-Vi = Uiiv,^,Vi,2, ■ ■ ■ ,vi;r), kde rii bývá buď konstanta nebo proměnná pro danou množinu nabývající hodnot n>i > Kí, 1 < rii < k. Regulárni jazyk pro rii ■ v;t vytvoříme takto: ax a2 ... ar ■ a2 ... ar ) Tyto regulární jazyky vektorů lineární množiny spojíme operátorem +. Vzniknou dílčí regulární jazyky pro jednotlivé lineární množiny Ty taktéž spojíme operátorem + (pro připomenutí - tento operátor odpovídá sjednocení). □ Důsledek 1.4 Nad jednoprvkovou množinou bezkontextovost nepřidá na generativní síle, tj. každý bezkontextový jazyk nad jednoprvkovou abecedou je zároveň regulární. Když takový jazyk není regulární, tak není ani bezkontextový (je kontextový nebo typu 0). Důkaz: Důkaz je triviální - v důkazu věty 1.3 jsme vlastně „přemísťovali" jednotlivé symboly v definici jazyka. Když však tímto způsobem proházíme symboly v definici jazyka nad jednoprvkovou abecedou, generovaný jazyk se nezmění (například a1+2n pro n > 0 je totéž jako a(aa)*). Zřejměji je možné si tento postup ukázat na pravidlech - když máme bezkontex-tové pravidlo A —► áLBa^ pro A, B E N, T = {a}, indexy i, j > 0, pak ekvivalentní regulární pravidlo vytvoříme přesunem: A —► ála?B, případně řetězec symbolů a rozdělíme s použitím pomocných neterminálů. Proto pro každou bezkontextovou gramatiku nad jednoprvkovou abecedou existuje regulární, která je s ní ekvivalentní. □ 1.1.3 Dyckův jazyk Dyckovy jazyky se také nazývají dobře uzávorkované jazyky. Jde vlastně o jazyky nad abecedou uspořádaných dvojic znaků odpovídajících levým a pravým závorkám různých typů. Kapitola 1 Vlastnosti bezkontextových jazyků 13 Definice 1.5 (Dyckův jazyk) Nechť En = {aľ, a[, a2, a!2,... ,an,a'n}, |En| = 2n je abeceda, n > 1. Dyckův jazyk nad touto abecedou je jazyk generovaný gramatikou s pravidly S —► aiSa'-L | a2Sa'2 | ... | anSa'n \ SS \ e Příklad 1.10 S2 {(,),[,]}(n = 2,|E2|=4) S (S) [S] SS S^SS^(S)S^([S] )S=>([])S=>([])[S\ =>([])[] Lemma 1.5 (Vlastnosti Dyckova jazyka) Nechť D n je Dyckův jazyk nad abecedou En. Pak pro jakákoliv dvě slova u^eE* platí 1. Jestliže u, v G Dn, pak u ■ v G Dn. 2. Jestliže u G Dn, pak u ■ a- G Dn, 1 < i < n. 3. Každé slovo w G Dn, w ^ e jeve tvaru u ■ a^v pro nějaké 1 < i < n, u, v G Dn. 4. Jestliže a• • u G -Dn/ pafc u 1} Vybereme vhodný regulární jazyk R, homomorfismus ip a Dyckův jazyk D: R = aa*bb* (dodá základní tvar slov - nejdřív a a potom b) p je identita, D = {{S}, {a, b}, P, S), kde P = {S aSb | SS | e} Kapitola 1 Vlastnosti bezkontextových jazyků 14 Pak je zřejmé, že L\ = R n D. Jiný možný výběr: R= [* ]* D = ({S}, {[,]}, P, S), kde P {s ^[S] SS e} Příklad 1.12 - L8 = {a^V1-1 I n > 1} R = 230*1*, jazyk D má pravidla P = {S ->■ 051 | 253 | SS \ e} 99(0) = aa, ip{l) = b, ip{2) = a, 99(3) = e Příklad 1.13 - Dokážeme, že jazyk L2 = {anbncn \ n > 0} není bezkontextový V předchozích příkladech jsme mohli pozorovat, že regulární jazyk zajišťuje správnou posloupnost symbolů a Dyckův jazyk synchronizuje počet symbolů v jednotlivých podskupinách. Správnou posloupnost symbolů by mohl zajistit regulární jazyk R = a*b*ď, ale nedokážeme najít Dyckův jazyk tak, aby dokázal synchronizovat tentýž počet symbolů na více než dvou místech. Proto L2 ^ Jr(CF). 1.2 Jak poznat zda je jazyk bezkontextový Nejlepším způsobem, jak určit, že je jazyk bezkontextový, a také prakticky jediným přímým důkazem, je sestrojení bezkontextové gramatiky generující tento jazyk. V předchozích sekcích jsme si ukázali tři metody, které lze využít při důkazu sporem - Pumping lemma, Parikhův vektor jazyka a Dyckův jazyk. Ve všech třech případech jde o implikace, proto nejsou použitelné pro přímý důkaz. Existuje však další možnost - využití uzáverových vlastností bezkontextových jazyků. Bezkontextové jazyky jsou například uzavřeny vzhledem k operaci sjednocení, a tedy pokud lze některý jazyk napsat jako sjednocení dvou bezkontextových Kapitola 1 Vlastnosti bezkontextových jazyků 15 jazyků, pak jde o bezkontextový jazyk. Uzáverovým vlastnostem bezkontextových jazyků se budeme věnovat v sekci 1.3. 1.3 Uzáverové vlastnosti bezkontextových jazyků Ve větách a důkazech této sekce budeme používat následující značení (nesouvisející s průběžným číslováním jazyků v tomto dokumentu): L1 = L(G1), G^iNuTuPuSJ L2 = L(G2), G2 = (N2,T2,P2,S2), iVxUiV2 = 0 vytváříme L = L (G), G = (N, T, P, S) Narozdíl od regulárních jazyků, zde budou důkazy postaveny na konstrukci gramatik, ne automatů. 1.3.1 Regulární operace Věta 1.7 Třída bezkontextových jazyků je uzavřena vzhledem k operaci sjednocení. Důkaz: Vytvoříme gramatiku G takovou, že L(G) = Li U L2: G = (N, T, P, S), symbol S <£ Nľ U N2 (nově přidaný), T = T1U T2l N = N1UN2U {S}, p = p1 u p2 u {s S! | s2} Přejímáme zde vše z původních gramatik, změna je jen na začátku derivace - prvním krokem derivace je rozhodnutí, zda bude generováno slovo z prvního nebo z druhého jazyka. Pak je provedena simulace činnosti některé z původních gramatik (resp. je předáno řízení některé z původních gramatik). □ Příklad 1.14 - Jazyk L9 = {áLlýck \ i,j, k > 1, i = j nebo j = k} lze napsat jako sjednocení dvou bezkontextových jazyků Lx U Ly, kde Lx = {éWck \ i,j,k >1, i = j} Ly = {áLVck | i,j, k > 1, j = k} (gramatiky viz příklad 1.16 na straně 17) Kapitola 1 Vlastnosti bezkontextových jazyků 16 Věta 1.8 Třída bezkontextových jazyků je uzavřena vzhledem k operaci zřetězení. Důkaz: Vytvoříme gramatiku G takovou, že L(G) = Lx- L2: N = N1UN2U {S}, S iVi U N2 p = p1up2u{s -> 5X • s2} T = T1UT2} □ Věta 1.9 Třzdfl bezkontextových jazyků je uzavřena vzhledem k operaci iterace (Kleeneho uzávěru, operace hvězdička). Důkaz: Vytvoříme gramatiku G takovou, že L(G) = L\: N = N1U{S}, S<£N1} T = Ti, p = p1 u {S SXS \ e} □ 1.3.2 Operace, vzhledem k nimž je ještě třída Jšf (CF) uzavřena Věta 1.10 Třída bezkontextových jazyků je uzavřena vzhledem k operaci pozitivní iterace. Důkaz: Vytvoříme gramatiku G takovou, že L(G) = L\\ N = N1U{S}, S<£N1} T = Ti, p = p1 u {s sxs I Si} □ Věta 1.11 Třída bezkontextových jazyků je uzavřena vzhledem k operaci zrcadlení (reverze). Důkaz: Vytvoříme gramatiku G takovou, že L(G) = Lf: N = Nu T = Ti, S = Si Každé pravidlo z původní množiny pravidel převrátíme - přeneseme reverzi na pravidla: p = {A ->■ aR \ (A ->■ a) G pu A G Nu a G (iV U T)*} □ Příklad 1.15 - Pravidlo A —► abbBcaCacb bude po reverzi a —► bcaCacBbba. Kapitola 1 Vlastnosti bezkontextových jazyků 17 Příklad 1.16 - Re verzi si ukážeme na tomto jazyce: L9 = {áLVck | i,j, k > 1, i = j neboj = k} Jazyk Lg lze generovat bezkontextovou gramatikou s pravidly S ->■ Si | S2 A^aAb\ab X ->■ cX | c 5i ->■ AX B ^bBc\bc Y ^aY \a S2^YB Ukázka derivace: S =>■ S*! =>■ AX =>■ aA&X =>■ aabbX =>■ aa&6c Po re verzi: 5 ->■ Si | S2 A ->■ 6Aa | 6a X ->■ Xc | c 51 ->■ XA B ^cBb\cb Y ->■ Fa | a 52 ^ Ukázka derivace: £ Si =>- XA =>■ X&Aa =>■ Xbbaa =>■ c66aa Generovaný jazyk je Lf = {ckVáL \ i,j,k > 1, i = j nebo j = k} a stejně jako původní jazyk, i tento je bezkontextový (existuje bezkontextová gramatika, která ho generuje). Věta 1.12 Třída bezkontextových jazyků je uzavřena vzhledem k operaci bezkontextové substituce. Důkaz: Bezkontextová substituce s je takové zobrazení, které zobrazuje každý symbol původní abecedy na bezkontextový jazyk a přitom platí s(e) = e, s (a ■ v) = s (a) ■ s(v), a G (N U T), v G (N U T)* NechťLi je bezkontextový jazyk nad abecedou E = {a1; a2,..., an} a jsou dány bezkontextové jazyky Ji, J2,...,Jn nad abecedami E1; E2,..., En tak, že s(a,i) = Jir v každém jazyce Si je startovacím symbolem a^, 1 < -i < n. Pro všechny bezkontextové jazyky J i existují bezkontextové gramatiky Gji = (Nj., Ej, Pj., a,i) a předpokládejme, že množiny jejich neterminálních symbolů jsou po dvou disjunktní a taktéž průnik kterékoliv z těchto množin neterminálů s množinou N\ je prázdný. Jazyk L = s(Li) sestrojíme takto: N = Xi U {ai, a2,..., an} U Uľ=i ^ Kapitola 1 Vlastnosti bezkontextových jazyků 18 T = Uľ=i S, p = p1u{jr:=1pJi □ Příklad 1.17 - Postup si ukážeme na bezkontextovém jazyku L9 = {áLVck | i, j, k > 1, i = j neboj = k} Gi = ({S, A, B, X, Y}, {a, b, c}, P1, S) av množině P\ jsou pravidla S ->■ AX | Y B A^aAb\ab X ->■ cX | c B ^bBc\bc Y ->■ aF | a Substituce: = {1" | n > 0}, GJa = ({a}, {1}, {a -+ la | e}, a) s(6) = {l"0n | n > 1}, GJb = ({6}, {1, 0}, {6 -+ 160 | 10}, 6) s(c) = {0™ | n > 0}, GJc = ({c}, {0}, {c -+ 0c | e}, c) Po provedení substituce: G = ({S, A, B, X, Y, a, b, c}, {0,1}, P, S) av množině P\ jsou pravidla S ^ AX \YB X ^cX | c a^la\e A^aAb\ab Y ^ aY \ a b ->■ 160 | 10 5 —► 65c | 6c c —► 0c | £ Generovaný jazyk je L = s(L9) = 1* • {ln0n | n > 1}* • 0* Poznámka: Protože homomorfismus je vlastně speciálním případem substituce (jde o jednoznačnou substituci, kdy jednomu symbolu přiřazujeme právě jedno slovo, tedy jednoprvkový jazyk), znamená to, že třída bezkontextových jazyků je uzavřena i vzhledem k operaci homomorfismu. 1.3.3 Operace, vzhledem k nimž třída J£{CF) není uzavřena Věta 1.13 Třída bezkontextových jazyků není uzavřena vzhledem k operaci průniku. Důkaz: Najdeme dva bezkontextové jazyky, jejichž průnikem je jazyk, který není bezkontextový Lx = {a%b%é | i, j > 0} (počet a je stejný jako počet 6) Ly = {albkck | i, j > 0} (počet 6 je stejný jako počet c) Kapitola 1 Vlastnosti bezkontextových jazyků 19 Průnikem těchto jazyků je L = Lx fl Ly = L2 = {anbncn \ n > 0}, o kterém jsme již dříve dokázali, že není bezkontextový (v příkladech 1.2 na straně 7 a 1.13 na straně 14). Všimněme si, že sjednocením těchto jazyků je bezkontextový jazyk Lg U {e} = {áLVck | i, j, k > 0, i = j neboj = k}. □ Věta 1.14 Třída bezkontextových jazyků není uzavřena vzhledem k operaci doplňku (kom-plementu) nad danou abecedou. Důkaz: Využijeme již dokázaná tvrzení z předchozích vět, konkrétně to, že třída bezkontextových jazyků je uzavřena vzhledem ke sjednocení, ale není uzavřena vzhledem k průniku. Podle DeMorganových pravidel, která si jistě pamatujeme z teorie množin nebo algebry (jazyky vlastně nejsou nic jiného než množiny slov), platí L1nL2=T1UL2~ (1.4) Předpokládejme, že třída bezkontextových jazyků je uzavřena vzhledem k operaci doplňku (důkaz sporem). Pak na pravé straně rovnice (1.4) máme množinu bezkontextových jazyků. Jenže na levé straně rovnice je množina, ve které existují i jazyky, které nejsou bezkontextové (průnikem dvou bezkontextových jazyků může být i jazyk, který není bezkontextový), což je spor. □ 1.4 Uzáverové vlastnosti jako kritérium bezkontexto-vosti Většina uzáverových vlastností se dá použít v přímém důkazu: Příklad 1.18 - Zjistíme, zda je následující jazyk bezkontextový: L13 = {anibnian2bn2 ... aHkbnk | k > 0, m > 1, 1 < i < k} Víme, že jazyk L\ = {cŕb11 \ n > 1} je bezkontextový, a je zřejmé, že Lí3 = L\ a proto i jazyk L13 je bezkontextový. Kapitola 1 Vlastnosti bezkontextových jazyků 20 Nesmíme zapomenout, že vlastně ani uzáverové vlastnosti nejsou ekvivalence, ale pouze implikace (jestliže Lľ a L2 jsou bezkontextové, pak ...). Důsledky můžeme vidět na příkladu Příklad 1.19 - Víme, že jazyk L3 = j a™2 n > 0 j není bezkontextový (to jsme dokázali v příkladu 1.3 na straně 7 pomocí Pumping lemma). Zvolíme následující bezkontextovou (dokonce regulární) substituci: s(á) = b* Po uplatnění substituce dostaneme jazyk {bl \ i > 0}, což je bezkontextový (dokonce regulární) jazyk. Proto není pravda, že když je výsledkem operace bezkontextový jazyk, tak by operandy operace měly být také. Q x r*, lze zapsat také jako ô{qi, a, Z) 3 (qj, 7), qu qj E Q, a G (E U {e}, Z e T, -f e T*. Zásobníkový automat je obecné nedeterministický. Definice 2.2 (Konfigurace zásobníkového automatu) Konfigurace výše definovaného zásobníkového automatu A je Q x "Ľ* x T* (také (g, a, 7), q G Q, a G E*, 7 G r*). Počáteční konfigurace je (q0, w, Z0), kde w je slovo, které bylo dáno na vstup automatu. Koncová konfigurace závisí na typu zásobníkového automatu. První člen konfigurace je stav, ve kterém se automat právě nachází, druhý je nepřečtená část vstupní pásky a třetí momentální obsah zásobníku. Definice 2.3 (Přechod mezi konfiguracemi) Přechod mezi konfiguracemi zásobníkového automatu je relace (q,t, aa, Zj3) h (gi; a, 7/?) <í=> (gi; j3) G 5(qh a, Z) kde a e Ľ U {e}, Z eTU {e}, a G E* Symbol h* značí reflexivní tranzitivní uzávěr relace h*, symbol h+ je tranzitivní uzávěr této relace (jakýkoliv počet přechodů, alespoň jeden), symbol P znamená přesně i přechodů mezi konfiguracemi. Kapitola 2 Zásobníkový automat 23 Definice 2.4 (Základní typy zásobníkových automatů) Rozeznáváme tyto základní typy zásobníkových automatu: Zásobníkový automat končící přechodem do koncového stavu je Af s koncovou konfigurací (Qf,£,7), Qf e F, 7 G T* a rozpoznávaný jazyk je L(AF) = {w G E* | (q0,w,Z0) h* (g/,£,7), 9/^,76 t*} Zásobníkový automat končící s prázdným zásobníkem je A% s koncovou konfigurací (q, e, e), q e Q a rozpoznávaný jazyk je L(A%) = {w G E* | (q0, w, ZQ) h* (q, e, e), q E Q} Zásobníkový automat končící přechodem do koncového stavu a prázdným zásobníkem je Af,® s koncovou konfigurací (g/, e, e), q f G F a rozpoznávaný jazyk je L(AF,y>) = {w G E* | (q0,w,Z0) h* (qf,e,e), qf G F} Jak vidíme, tyto tři základní typy se liší především svou koncovou konfigurací: • zásobníkový automat končící v koncovém stavu ukončí výpočet ve chvíli, kdy má přečtenou celou vstupní pásku (prostřední člen konfigurace je e) a nachází se v některém koncovém stavu, • zásobníkový automat končící s prázdným zásobníkem končí výpočet, když má přečtenou celou vstupní pásku a zároveň je prázdný zásobník, • třetí typ je kombinací (průnikem) obou předchozích - musí být splněny obě podmínky Všechny tři typy zásobníkových automatů končí samozřejmě výpočet i tehdy, když nejsou v žádné koncové konfiguraci, ale do žádné další se nemohou dostat (přechodová funkce nedává možnost reagovat v daném stavu s daným obsahem zásobníku a vstupní pásky). Kapitola 2 Zásobníkový automat 24 Příklad 2.1 - Sestrojte zásobníkový automat (dále ZA) končící s prázdným zásobníkem rozpoznávající jazyk L14 = {wcwR I w E {a, &}*} Vytvoříme zásobníkový automat rozpoznávající prázdným zásobníkem: M = ({qo,qi}, {a,b}, {a,b,Z0}, q0, Z0, ô, 0) Automat bude pracovat takto: • v první fázi bude číst obsah vstupu (první polovina slova) a ukládat do zásobníku (vždy co v každém kroku vyjmeme, vrátíme do zásobníku zároveň se symbolem ze vstupu, tedy ukládáme dva symboly), jsme ve stavu q0, • díky principu zásobníku (čteme v opačném pořadí, než jak byly symboly uloženy) je ukládaná první polovina slova zároveň zrcadlově převrácena, • když na vstupu narazíme na c (hranice, polovina slova), přejdeme do stavu qi a tím změníme způsob práce automatu, • když jsme ve stavu q\, nic do zásobníku neukládáme, symbol, který v každém kroku vyjmeme, porovnáme s tím, co je na vstupu - když souhlasí, můžeme pokračovat (tj. v každém kroku se posuneme na vstupu a zároveň ubereme symbol ze zásobníku). 6(q0, a, ZQ) = (q0, aZ0) na začátku výpočtu, slovo začíná a ô(q0, b, Z o) = (q0, bZ0) na začátku výpočtu, slovo začíná b ó(q0, a, X) = (q0, aX), X E {a, b] zatím jen načítáme a ukládáme do zásobníku ô(q0,c,X) = (q1,X), X E {a, b} jsme na hranici 6(qi, a, a) = (qi,e) shoda a v obou polovinách slova 6(qi, b, b) = (qi,e) shoda b v obou polovinách slova ô(qi,e, Z o) = (qi, e) skončili jsme na vstupu i v zásobníku Ukázka výpočtu automatu na slovo abcba: (q0, abcba, Z0) h (q0, bcba, aZ0) h q0 : přenášíme do zásobníku obsah vstupu h (q0, cba, baZ0) h hraniční bod, přejdeme do módu qi h (qi,ba, baZ0) h (q1, a, aZ0) h q1 : jen vybíráme ze zásobníku a porovnáváme h (gi, e, Z0) h (gi, e, e) konec Kapitola 2 Zásobníkový automat 25 Poznámka: Zásobníkový automat končící v koncovém stavu (a vlastně i „hybridní" typ) bychom z předešlého vytvořili jednoduše - stačí poslední část definice ô funkce přepsat takto: 5(que, ZQ) = (q2, e) s tím, že Q = {q0, qu q2}, F = {q2}. Příklad 2.2 - Vytvořte zásobníkový automat končící v koncovém stavu reprezentovaný stavovým diagramem pro jazyk z příkladu 2.1 Li4 = [wcwR I w e {a,&}*}. Narozdíl od konečných automatů, u zásobníkových nám nestačí ohodnotit šipky pouze symbolem načítaným ze vstupní pásky Musíme vždy zadat tři údaje (ve správném pořadí!) • symbol načtený ze vstupu (nebo e, když ze vstupu nic nenačítáme), • symbol, který vyjímáme ze zásobníku (nesmí zde být e\, v každém kroku musíme nějaký symbol vyndat), • řetězec, který ukládáme do zásobníku. Diagram vytvoříme podle 5 funkce v příkladu 2.1, jen navíc zakomponujeme změnu zahrnutou v poznámce nad tímto příkladem. Výsledný diagram vidíme na obrázku 2.1. 2.2 Vztah mezi různými typy zásobníkových automatů Zde se podíváme na vztahy mezi třídami jazyků generovaných zásobníkovými automaty končícími v koncovém stavu, prázdným zásobníkem a nebo obojím. X g {a, b, Z0} Obrázek 2.1: Diagram zásobníkového automatu Kapitola 2 Zásobníkový automat 26 V dalším textu budeme používat toto označení: ££F = {L | L = L(Af) pro nějaký zásobníkový automat Af} ...................Třída jazyků generovaných ZA končícími v koncovém stavu J2?0 = {L | L = L (A®) pro nějaký zásobníkový automat A®} ..............Třída jazyků generovaných ZA končícími prázdným zásobníkem á?F,d = {L \ L = L(Af$) pro nějaký zásobníkový automat Af} ......Třída jazyků generovaných ZA končícími v koncovém stavu s prázdným zásobníkem Veta 2.1 Nechť A = (Q, S, ľ, q0, Z0, ô, 0) je ZA končící výpočet prázdným zásobníkem. Potom existuje ZA A = (Q', S, T', q'Q, Z'Q, ô', F) končící výpočet v koncovém stavu takový, že L (A) = L (A). To znamená, že pro třídy jazyků generovaných jednotlivými typy ZA platí relace -S?0 C &F (2.1) Důkaz: Budeme postupovat takto: • do zásobníku dáme pomocnou „zarážku" (počáteční zásobníkový symbol původního automatu Z0) a dále budeme simulovat výpočet původního automatu, • simulovaný výpočet probíhá nad vloženou „zarážkou" a končí ve chvíli, kdy je tato zarážka vyjmuta (v té chvíli má simulovaný automat prázdný zásobník), v zásobníku je pouze Z'Q (počáteční zásobníkový symbol nového automatu), • pak jen přejdeme do koncového stavu; pokud je celá vstupní páska přečtená, pak končí výpočet s úspěchem, slovo je přijato. Q'= QU{q'0,qf}, q'Q{Q,qfÍQ F = {qf} T' = TU{Z>} Funkci ó' definujeme takto: • na začátku výpočtu přidáme do zásobníku počáteční zásobníkový symbol původního automatu, abychom mu pro simulaci připravili vhodné pracovní prostředí: Kapitola 2 Zásobníkový automat 27 • potom simulujeme činnost původního automatu (tj. přejmeme chování jeho ô funkce): ô'(g, a, z) = ô{q, a, z) Vg G Q, a G E U {e}, z G T • po ukončení výpočtu původního automatu přejdeme do koncového stavu: S'(q,e,Z'0) = (qf,e) Přechod mezi konfiguracemi bude následující: w> z'o) h (Qo, w> zoK) h • • • původní výpočet ...h (q, e, Z'Q) h (qf, e, e) □ Veta 2.2 Nechť A = (q, E, ľ, g0, Z0,5, f) je za končící výpočet v některém koncovém stavu. Potom existuje za A' = (q', E, T', q'0,ZQ, ô', 0) končící výpočet prázdným zásobníkem takový, že L(A') = L (A). To znamená, že pro třídy jazyků generovaných jednotlivými typy za platí relace C &i (2.2) Důkaz: Abychom se v průběhu výpočtu „náhodou" nedostali na dno a tak předčasně neukončili výpočet, tak stejně jako v předchozím důkazu do zásobníku dáme pomocnou „zarážku" (počáteční zásobníkový symbol původního automatu Z0) a dále budeme simulovat výpočet původního automatu. Nejdřív si definujeme funkci ó': • na začátku výpočtu přidáme do zásobníku počáteční zásobníkový symbol původního automatu: $'(qÍ£,zo) = (qo,z0z^) • potom simulujeme činnost původního automatu: ô'[q, a, z) = ô{q, a, Z) Vg G Q, a G E U {e}, z G T • po ukončení výpočtu původního automatu vyprázdníme zásobník, ale nesmime zapomenout na to, že simulovaný automat by v koncovém stavu ještě mohl chtít pracovat (stav, ve kterém bude mazán zásobník, je d - delete): ó'(qf,s,z)=ó(qf,s,z)U{(d,s)} ô'{d,e,Z) = {d,e), \/z G ľ" Q' = QU{q'0,d}, q'0£Q,d£Q, T' = TU{z'0} Přechod mezi konfiguracemi bude následující: (q'0, w, Z'Q) h (g0, w, ZQZ'Q) h ... původní výpočet... h (qf, e, ZaZ'Q) h h (d, e, a Z q) h ... h (d, e, e) □ Kapitola 2 Zásobníkový automat 28 Důsledek 2.3 Třídy jazyků generovaných zásobníkovými automaty končícími v koncovém stavu a zásobníkovými automaty končícími s prázdným zásobníkem jsou ekvivalentní: ££p = J£% (2.3) Dále z vlastností zásobníkových automatů generujících jazyky z třídy J£F# plyne, že &Fíb = if0 = £>F (2.4) Množinu všech zásobníkových automatů budeme souhrnně označovat ZA, třídu (množinu) jazyků rozpoznávaných zásobníkovými automaty Jŕ(ZA). 2.3 Vztah zásobníkových automatů a bezkontextových jazyků Nadále budeme počítat s tím, že zásobníkové automaty všech tří základních typů jsou navzájem ekvivalentní, a tedy generují stejné třídy jazyků. Proto v důkazech budeme volně tyto typy zaměňovat. Věta 2.4 Ke každé bezkontextové gramatice G lze vytvořit zásobníkový automat A takový, že L(G) = L(A), tedy Jŕ{CF) C J?(ZA) (2.5) Důkaz: Máme bezkontextovou gramatiku G = (N, T, P, S) a chceme sestrojit zásobníkový automat A = (Q, S, ľ, q0, Z0, ô, 0) (automat končí s prázdným zásobníkem). Budeme postupovat takto: • v zásobníku mohou být neterminály a terminály, ze kterých se skládají pravidla, pravé strany pravidel ukládáme do zásobníku, • pokud je na vrcholu zásobníku neterminál, vyjmeme ho a nahradíme pravou stranou některého pravidla přepisujícího tento neterminál, • pokud ze zásobníku vyjme terminálni symbol, načte symbol ze vstupu a porovná - pokud jsou stejné, může dál pokračovat (do zásobníku už vyjmutý symbol nevrací, a na vstupu se při přečtení vstupního symbolu posune na další). Kapitola 2 Zásobníkový automat 29 Q = { 0, k > 0} Tento jazyk rozpoznává zásobníkový automat .A =({0,1}, {a,b,c}, {Z0,a}, Ö, 0, Z0, 0) 0(0, a, X) = (0, aX), X E {a, Z0} o(0,c,X) = (l,X), Xe{a,Z0} ö(l,b,a) = (l,e) ö(l,c,Z0) = {(l,Z0), (l,e)} Vytvoříme automat A': Ö1 Ö1 s,a, [0,X,0]) s,a, [0,X,1]) { { (■ (■ s, [0, a, 0] [0, X, 0]), (s, [0, a, 1] [1, X, 0])} , X E {a, Z{ s,[0,a,0][0,X,l]), (s,[0,a,l][l,X,l])} 'o} Ö1 Ö1 s,c, [0,X, 1]) s, [1,X, 1])} Ö1 Ö1 Ö1 Kapitola 2 Zásobníkový automat 32 Nové zásobníkové symboly jsou možná přehledné z hlediska vytvoření, ale bude lepší nahradit je kratšími variantami podle následující tabulky Dlouhé označení— -^Krátké označení [0,Z0,0] - -»■ A [o,z0,i] - ->■ B [l,Z0,0] - -»• C [l,Z0,l] - ->■ D [0,a,0] - ->■ E [0,a,l] - ->■ F [l,a,0] - -»• G [l,a,l] - ->■ LT Upravíme 5' funkci: s,e,ZÓ) = {(s,A), (s, B)} 5'{ s,a,A) = {(s,EA), (s,FC)} 5'(s,c,A) = {(s,C)} ö'{ s,a,E) = {(s,EE), (s,FG)} ö'(s,c,E) = {(*,G)} 5'{ s,a,B) = {(s,EB), (s,FD)} ö'(s,c,B) = {(s,D)} 5'{ s,a,F) = {(s,EF), (s,FH)} ö'(s,c,F) = {(s, H)} S'( s,b,H) = {(s,s)} ö'{s,c,C) = {(s,C)} ö'(s,c,D) = {(s,D), (s,e)} Automat potom můžeme určit takto: A' = (W, M c}, {Z'0,A,B,C,D,E F, G, H}, 5', ■s, Z'0, 0) Ukázka rozpoznání slova aacbbc automatem A: (0, aacbbc, Zq) h (0,acbbc,aZo) h (0,cbbc,aaZo) h (1, bbc, aaZo) h (1, h (l,c,Z0) h (1,e,e) Ukázka rozpoznání slova aacbbc automatem A': aacbbc, Z'0) h (s, aacbbc, B) h (s, acbbc, F D) h h (s, ebbe, F H D) h (s, bbc, H H D) h (s, bc, HD) h (s, c, D) h (s, e, e) Totéž, ale bez nahrazení zásobníkových symbolů kratšími verzemi: (s, aacbbc, Z'0) h (s, aacbbc, [0, Z0, l]j h (s, acbbc, [0, a, 1] [1, Z0, ljj h h (s, c66c, [0, a, 1] [1, a, 1] [1, Z0,1]) h (s, 66c, [1, a, 1] [1, a, 1] [1,Z0,1]) h h (s, 6c, [l,a,l][l,Z0,l]) h (s, c, [1,Z0,1]) \-(s,e,e) Kapitola 2 Zásobníkový automat 33 Veta 2.6 Ke každému zásobníkovému automatu A existuje bezkontextová gramatika G taková, že L (G) = L (A), tedy Jŕ{ZA) C J?(CF) (2.6) Důkaz: Když jsme dokazovali, že ke každé bezkontextové gramatice lze sestrojit ekvivalentní zásobníkový automat (v důkazu věty 2.4 na straně 28), vytvořili jsme jednostavový zásobníkový automat. Zde využijeme přesně opačný postup - podle jednostavového automatu vytvoříme gramatiku. Prvním krokem tedy bude vytvoření jednostavového zásobníkového automatu A' k automatu A podle postupu popsaného v důkazu věty 2.5. V druhém kroku vytvoříme gramatiku, jejíž neterminály vytvoříme ze zásobníkových symbolů. Když oba kroky shrneme, postup je následující: 1. Inicializujeme výpočet: MqeQ : S [q0,Z0,q] 2. Pro všechny funkce automatu A ve tvaru 6(p, a, Z) 3 (q, e) (do zásobníku nic nevkládají) vytvoříme [p, Z,q]^a 3. Pro všechny ostatní funkce ve tvaru 6(p, a, Z) 3 (q, B\B2 ■ ■ ■ Bn): [p, Z,un] —► a[q,B1,u1][u1,B2,u2] ... [wn-i, Bn, un] pro každou kombinaci stavů Ui E Q, 1 < i < n. □ Příklad 2.5 - Budeme pokračovat v příkladu 2.4 na straně 31. V zadání příkladu byl automat .A =({0,1}, {a,b,c}, {Z0,a}, Ô, 0, Z0, 0) 5(0, a, X) = (0, aX), X e {a, Z0} o(0,c,X) = (l,X), Xe{a,Z0} ó(l,b,a) = (l,s) S(l,c,Z0) = {(l,Z0), (l,e)} Kapitola 2 Zásobníkový automat 34 Podle popsaného postupu vytvoříme gramatiku G = (N, T,P,S), T = E, s pravidly S^[0,Z0,0] | [0,Z0,1] [0,Z0,0] ^a[0,a,0][0,Z0,0] | a[0, a, 1] [1, Z0,0] [0,a,0] ->■ a[0,a,0][0,a,0] a[0, a, 1] [1, a, 0] [0,Z0,1] ^a[0,a,0][0,Z0,l] | a[0, a, 1] [1, Z0,1] [0, a, 1] —► a[0, a, 0][0, a, 1] a[0, a, 1] [1, a, 1] [0,Z0,0] ^c[l,Z0,0] c[l, a, 0] -c[l,Z0,l] c[l,a, 1] b [0,a,0]-[0,Z0,1] [0,a,l]- [l,a,l]- [1,^0,0] [l,^o,l] c[l,Z0,0] c[l,Z0,l] Zjednodušíme neterminály a shrneme pravidla přepisující stejný neterminál: S A B A I B aEA I aFC \ cC aEB I aFD \ cD C ^cC D ^cD\c E ->■ aFF I aFG | cG aEF I aFF | cH b Neterminály: N = {S, B, C, D, F, H} Ukázka generování slova aacbbc: S B aFD aaFHD aacHHD =>- aacbbcD =>- aacbbcc F H Odstraníme nadbytečné symboly: 5 ->■ aFD I cD C ^cC D ->■ cF> | c F ->■ aFF I aacbHD =>- aacbbD Dá se jednoduše dokázat, že generovaný jazyk je L15 = {ancbnck | n > 0, fc > 0} Kapitola 2 Zásobníkový automat 35 Důsledkem vět 2.4 na straně 28 a 2.6 na straně 33 je ekvivalence tříd jazyků: Důsledek 2.7 Jŕ{ZA) ~ Jŕ{CF) (2.7) 2.4 Zásobníkové automaty a uzáverové vlastnosti bez-kontextových jazyků V sekci 1.3 na straně 15 jsme probrali téměř všechny operace, vzhledem k nimž je nebo není třída bezkontextových jazyků uzavřena, a dokázali jsme (věta 1.13 na straně 18), že třída bezkontextových jazyků není uzavřena vzhledem k operaci průniku. To však neplatí pro průnik s regulárním jazykem: Věta 2.8 Třída bezkontextových jazyků je uzavřena vzhledem k průniku s regulárním jazykem. Důkaz: Narozdíl od jiných uzáverových vlastností bezkontextových jazyků, zde konstrukci nebudeme provádět na gramatikách, ale na automatech. Postup bude podobný tomu, který jsme použili v kurzu Teorie jazyků a automatů I pro průnik dvou regulárních jazyků. Vytváříme průnik bezkontextového jazyka reprezentovaného zásobníkovým automatem Ai a regulárního jazyka reprezentovaného konečným automatem A2: A\ = (Qi, Ei, ľi, ôi, q^\ Fi) (rozpoznává koncovým stavem) A2 = (Q2,Ľ2,ô2,qí2),F2) Sestrojíme A = (Q, E, T, ô, q0, Z0, F), L(A) = L(Ai) n L(A2). Je zřejmé, že E = Ex U E2, T = Tu Z0 = Z'Q. Výpočet v automatu A má být simultánní simulací obou původních automatů, slovo, které má být rozpoznáno, prostě zároveň dáme na vstup obou původních automatů a přijmeme ho, pokud v obou automatech bude existovat výpočet od počáteční k některé konečné konfiguraci. Stavy automatu ubudou uspořádané dvojice stavů původních automatů, první prvek je stav automatu Ai a druhý je stav automatu A2. Uspořádaná dvojice zachycuje, v jakém stavu v původních automatech je právě simulovaný výpočet. Q = {[qi,Q2] I qi e Qi, q2 e Q2} Množina koncových stavů: F = {[qi, q2] | qi E Fi, q2 E F2} Definujeme ó funkci: Kapitola 2 Zásobníkový automat 36 1. V každém kroku, ve kterém je čten symbol ze vstupu, se posouváme v obou simulovaných automatech, v tom zásobníkovém také pracujeme se zásobníkem -pro každé a G E, q1,p1 G Q1, q2,p2 G Q2, Z G T, 7 G r*: 5([qi,q2],a,Z) 3 Oi,p2],7) <*i(9i>a, Z) 3 (pu7), 52(g2,a) 3 p2 2. Vyřešíme odlišnost původních automatů při práci se vstupní abecedou. Zásobníkový automat nemusí v každém kroku číst ze vstupní pásky, kdežto konečný ano. Proto umožníme simulaci konečného automatu dělat £-kroky, při kterých nebude číst ze vstupní pásky ani provádět změnu stavu - pro každé q1,p1 G Qi, q2 G Q2, Z G T, 7 G T{: 5([qi,q2],£,Z) 3 ([pi,q2],l) ^(q^e, Z) 3 (pi, 7) □ Příklad 2.6 - Vezmeme bezkontextový jazyk L16 = \wwR \ w G {a, b}*} a regulární jazyk a*. Jejich průnikem je jazyk L17 = {ďlďl \ n > 0} = {a2n | n > 0} Sestrojíme automaty, L(A\) = L16: •Ai = ({9o,?i,?2}, {a, b}, {Z0,a,b}, 5U q0, Z0, {q2}), kde 5i(g0, a, Z0) = {(q0, aZ0)} či(g0, a, a) = {(q0, aa), (qi,e)} Ô!(qo, b, Zq) = {(q0, bZ0)} ô^qo, b, b) = {(q0, bb), (que)} Si(qo, a, b) = {(q0, ab)} 5^, a, a) = {(qu e)} ôi(qo, b, a) = {(q0, ba)} ô^, b, b) = {(qu e)} ôi(qi,e,Z0) = {(q2,e)} Konečný automat pro jazyk a* je velmi jednoduchý: M = (M {a}, ô2, r, {r}), kde ô2(r, a) = r Vytvoříme A= (Q, {a,b}, {Z0,a,b}, ô, [q0,r], Z0, F). ô([q0,r],a,Z0) = {[q0,r],aZ0])} Ještě doplníme: ó([q0,r],a,a) = {([q0,r],aa),([qi,r],e)} Q = {[q0,r], [qur], [q2,r]} S([qi,r],a,á) = {[qi,r],e)} p = {[q2,r]} ô([qi,r],e,Z0) = {([q2,r],e)} Jak vidíme, je jazyk L17 průnikem bezkontextového a regulárního jazyka, proto (i bez konstrukce automatu rozpoznávajícího tento jazyk) můžeme říci, že je to bezkontextový jazyk. Kapitola 2 Zásobníkový automat 37 Příklad 2.7 - Pomocí uzáverových vlastností dokážeme, že není bezkontextový jazyk Li% = jw G {a, b, c}* \w\a = \w\b = |w|c| (stejný počet a, b a c) Předpokládejme, že jazyk L1S je bezkontextový Pak by průnikem tohoto jazyka s jakýmkoliv regulárním jazykem byl také bezkontextový jazyk. Vezmeme regulární jazyk R = a*b*c*. Jejich průnikem je L18 n R = L2 = {anbncn | n > 0} O tomto jazyce však víme, že není bezkontextový, proto L1S ^ Jr(CF). 2.5 Deterministické bezkontextové jazyky 2.5.1 Deterministický zásobníkový automat Definice 2.5 (Deterministický ZA) Zásobníkový automat A = (Q, S, ľ, 5, qo,Z0, F) je deterministický, jestliže pro každé q G Q, Z G ľ pZaŕz zároveň • 5(g, a, Z) má nejvýše jeden prvek pro každé a G S U {e}. • je-li 5(q, e, Z) Ý 0/ pak 5(q, a, X) = 0 Va G E. To znamená, že v deterministickém zásobníkovém automatu máme v každém kroku právě jednu možnost, jak reagovat (i včetně rozhodování, zda máme číst ze vstupní pásky). Definice 2.6 (Deterministický bezkontextový jazyk) Jazyk L se nazývá deterministický bezkontextový jazyk, jestliže existuje deterministický zásobníkový automat (DZA) Ad takový, že L(Ad) = L. Z definice vyplývá, že pro každé slovo patřící do jazyka existuje právě jeden výpočet v Ad- Deterministické bezkontextové jazyky budeme značit DCF a třídu jazyků, které generují, áf(DCF). Věta 2.9 Třída jazyk§ generovaných deterministickými zásobníkovými automaty je vlastní podmnožinou třídy bezkontextových jazyků: Jŕ{DCF) C Jŕ{CF) (2.8) Kapitola 2 Zásobníkový automat 38 Důkaz: To, že platí áf(DCF) C jšf (CF), je zřejmé - vyplývá to z toho, že deterministický zásobníkový automat je vlastně speciálním případem (obecného) zásobníkového automatu, a víme (viz důsledek 2.7), že třída jazyků generovaných bezkontextovými jazyky je ekvivalentní třídě jazyků rozpoznávaných zásobníkovými automaty. Vlastní inkluzi (tj. podmnožinu, Jŕ(DZA) C jšf (CF)) lze dokázat tak, že najdeme jazyk patřící do druhé, ale nepatřící do první třídy. Bezkontextovým jazykem, který není deterministickým bezkontextovým, je například Lie = {wwR | w e {a,b}*} (zásobníkový automat pro tento jazyk je v příkladu 2.6 na straně 36). Tento jazyk je velmi podobný jazyku Li4, ale slova nejsou v polovině rozdělena znakem c. Zásobníkový automat pro tento jazyk je možné sestrojit podobně jako pro jazyk L14 v příkladu 2.1 na straně 24, ale bude to rozhodně automat nedeterministický - nevíme, ve kterém okamžiku vlastně přecházíme do druhé poloviny rozpoznávaného slova (nemáme možnost si předem tuto informaci zjistit a obě poloviny slova mají podobnou strukturu), a proto v každém kroku při načítání první poloviny slova potřebujeme možnost nedeterministicky zvolit buď pokračování v první polovině slova, a nebo přechod do druhé. □ 2.5.2 Uzáverové vlastnosti deterministických bezkontextových jazyků Věta 2.10 Třída jazyků J^(DCF) je uzavřena vzhledem k operaci průniku s regulárním jazykem. Důkaz: Důkaz je stejný jako u (obecně) bezkontextových jazyků, viz věta 2.8 na straně 35. □ Věta 2.11 Třída jazyků J^(DCF) není uzavřena vzhledem k operaci průniku. Důkaz: Důkaz je stejný jako u (obecně) bezkontextových jazyků, viz věta 1.13 na straně 18. □ Dále budeme potřebovat tuto pomocnou větu (lemma): Kapitola 2 Zásobníkový automat 39 Lemma 2.12 Ke každému DZA A lze zkonstruovat DZA A', který každý vstup dočte do konce. Důkaz je složitý, je třeba vyřešit problém zacyklení v epsilonových krocích (práce se zásobníkem). Veta 2.13 Třída jazyků Jiť(DCF) je uzavřena vzhledem k operaci doplnku. Důkaz: Každý deterministický zásobníkový automat, který vstup dočte do konce, dokáže v konečném počtu kroků rozhodnout, zda slovo patří nebo nepatří do jazyka rozpoznávaného tímto automatem (lemma 2.12). Proto je postup následující: • sestrojíme k původnímu automatu A zásobníkový automat A', který čte každý vstup až do konce, • zaměníme koncové a nekoncové stavy. Věta 2.14 Třída jazyků áf(DCF) není uzavřena vzhledem k operaci sjednocení. Důkaz: Vyplývá z De Morganových zákonů: Předpokládejme, že třída jazyků Jzf(DCF) je uzavřena vzhledem k operaci sjednocení. Pak by na pravé straně vztahu (2.9) byla množina deterministických bezkontextových jazyků, jenže v množině na pravé straně rovnosti se mohou vyskytovat i jazyky, které nejsou deterministické bezkontextové (tato třída jazyků není uzavřena vzhledem k operaci průniku). Proto třída jazyků Jŕ(DCF) nemůže být uzavřena vzhledem k operaci sjednocení. □ □ Li n L2 = Lx U L2 (2.9) Důsledek 2.15 áf(DCF) c &(CF) (2.10) ■ p, a E (N Li T)*N(N U T)*, f3 E (N U T)* Definice 3.2 (Kurodova normální forma pro gramatiky typu 0) Gramatika typu Oje v KNF, jestliže pro všechna její pravidla a —► f3 platí \a\ < 2, \/3\ < 2. Veta 3.1 Ke každé gramatice G typu 0 lze sestrojit ekvivalentní gramatiku G' v KNF. Důkaz: • pravidla v bezkontextovém tvaru: použijeme algoritmus pro převod na Chomského NE • pravidla, která nejsou bezkontextového typu: upravíme pravidla podle následujícího algoritmu. Vstup: gramatika bez jednoduchých pravidel typu X —► Y, X,Y e N 40 Kapitola 3 Jazyky typu 0 41 1. Pro všechna pravidla: • Všechny terminály (na levé i pravé straně pravidla) a E T nahradíme „pomocnými" neterminály Na. • Pro všechny neterminály vytvořené v předchozím bodu přidáme pravidlo Na —► a. 2. Pravidla A —► BiB2 ... Bn, n > 2 nahradíme pravidly A ->■ BXXX X\ —> B2X2 X, n-2 -Bri—lBri 3. Pravidla AiA2 ... Am —► BiB2 ■ ■ ■ Bm, m > 2 nahradíme pravidly AľA2 XľA3 B1X1 B 2X2 Xm—2-Am ► Bm_\Bn 4. Nezkracující pravidla A±A2 ... Am —► BiB2 ... Bn, 2 < m < n nahradíme pravidly A1A2 —► B\X\ Xm-i —► BmXm X±A3 ~^ B2X2 Xm —► Bm+iXm+i Xm—2Am > Bm—\Xm—\ Xn—2 ^ Bn—iBn 5. Zkracující pravidla A\A2 ... Am —► B\B2 ■ ■ ■ Bn, n < m nahradíme pravidly AiA2 —► B1X1 XnAn+2 —► Xn+Í X1A3 —> B2X2 : : Y A _v Y Xn—\An^\ > BnXn Xm_2Am > £ □ Kapitola 3 Jazyky typu 0 42 Příklad 3.1 - Postup si ukážeme na gramatice S ->■ AaBC © C ->■ cBAa | bS ©,© AglBc d © Provedeme náhradu terminálů a E T novými neterminály Na. Týká se to pravidel © a ©• Pravidlo (3) nemusíme dále zpracovávat, už odpovídá Kurodově NF, po nahrazení terminálů je C —► iV^S*. Nejdřív zpracujeme pravidla bezkontextového typu © a ©. 5 -»■ AXi C -»■ XCX3 Xi —► XaX2 X3 —► BX4 X2 ^ X4 ^ AXa Zbývají pravidla © a @ - jedno je zkracující a druhé nezkracující: BA -+ NaX5 ANa -+ NdX7 NaXb -+ NbX6 X7B -+ X8 X6 -+ NcNd XSNC -+ s Celá gramatika po převodu do KNF: S - > ax1 x3^ BXA x6^ NcNd Na- a xx- -xax2 x4^ ANa AiVa" ^NdX7 Nb- ->■ 6 x2- -»■ £A - >ív„x5 x75 - Nc- -> c c- -ívcx3 NaXb ^x6x6 x8xc —► £ Nd- ->■ d 3.2 Stroje rozpoznávající jazyky typu 0 Existují dva typy strojů (resp. matematických modelů), které rozpoznávají jazyky typu 0 - zásobníkový automat rozšířený o další zásobník a Turingův stroj. 3.2.1 Zásobníkový automat se dvěma zásobníky Obecně můžeme mít jakýkoliv počet zásobníků, ale dá se dokázat, že k rozpoznávání jazyků typu 0 stačí dva zásobníky, resp. že ke každému zásobníkovému Kapitola 3 Jazyky typu 0 43 automatu s jakýmkoliv počtem zásobníků je možno vytvořit ekvivalentní (rozpoznávající stejný jazyk) se dvěma zásobníky Definice 3.3 (Zásobníkový automat se dvěma zásobníky) Zásobníkový automat se dvěma zásobníky je A2 = (Q, S, r1; T2, ô, q0, Z1, Z2, F), kde • Zi G Ti je počáteční zásobníkový symbol prvního zásobníku, abecedou prvního zásobníku je rl7 • Z2 G T2 je počáteční zásobníkový symbol druhého zásobníku, abecedou druhého zásobníku je T2, • ô funkce je definována takto: ó: Q x (E U {e}) x Ti x T2 ->■ Q x T* x T* 5(qu a, bu b2) G (q2,7i, 72), a G S U {e}, bľ G Tu b2 G T2, 7l G T*, 72 G T* • ese ostatní se přejímá z definice zásobníkového automatu (s jedním zásobníkem). Definice 3.4 (Konfigurace a přechod mezi konfiguracemi) Konfigurace zásobníkového automatu se dvěma zásobníky je (g)ffl)7l)72)eQxsřxr;xr; (stav, nepřečtená část vstupu, obsah prvního zásobníku, obsah druhého zásobníku). Přechod mezi konfiguracemi zásobníkového automatu se dvěma zásobníky je relace (ft,aQ!, 6171,6272) I- (Qj, Pili, P2I2) 5(qha,bub2) 3 (qjiPufo) Podobně jako u zásobníkových automatů s jedním zásobníkem bychom mohli definovat také reflexivní a tranzitivní uzávěr relace a také jazyk rozpoznávaný automatem, to necháváme na čtenáři, definice budou prakticky stejné. Příklad 3.2 - Vytvoříme zásobníkový automat se dvěma zásobníky pro jazyk, o kterém víme, že není bezkontextový: L2 = {anbncn I n > 0} M = ({9o, 9i,92>, {a,b,c}, {a,^}, {b,Z2}, Ô, Zu Z2, 0) ô funkce pracuje takto: • v první fázi (stav q0) načítáme symboly a a ukládáme je do prvního zásobníku, druhý zásobník zatím není používán, Kapitola 3 Jazyky typu 0 44 • v druhé fázi (stav gi) načítáme symboly b, přitom vyjímáme z prvního zásobníku symboly a (tak je zajištěn stejný počet a a b) a zároveň ukládáme symboly b do druhého zásobníku, • v třetí fázi (stav q2) musí již být první zásobník prázdný, načítáme ze vstupu symboly c a zároveň vyjímáme z druhého zásobníku symboly b (tak je zajištěn stejný počet bac). ó(q0, a, Zu Z2) = (q0, aZ1, Z2) 5(qu c, Zu b) = (q2, Zu e) ó(q0, a, a, Z2) = (q0, aa, Z2) ó(q2, c, Zu b) = (q2, Zu e) ô(q0, b, a, Z2) = (gi, e, bZ2) ô(q0, e, Z±, Z2) = (q0, e, e) č(gi, b, a, b) = (qu e, bb) ô(q2, e, Z±, Z2) = (q2, e, e) Ukázka rozpoznání slova aabbcc: (qo, aabbcc, Z±, Z2) h (go, abbcc, aZ±, Z2) h (go, bbcc, aaZ±, Z2) h (gi, bcc, aZ±, bZ2) h h (qi,cc, Zi, bbZ2) h (g2, c, Zľ, bZ2) h (g2, e, Zľ, Z2) h (g2, e, e, e) 3.2.2 Turingův stroj Činnost Turingova stroje jsme si již trochu osvětlili v kurzu Teorie jazyků a automatů I. Shrneme si základní vlastnosti: • konečná (konečněstavová) řídicí jednotka, • nekonečná páska (obvykle doprava nekonečná), • čtecí a zápisová hlava může číst symbol z pásky, přepsat ho jiným symbolem, pohybuje se o 1 políčko doleva nebo doprava, • výpočet končí při přechodu do některého koncového stavu, nemusí být přečtená celá páska. Definice 3.5 (Turingův stroj) Turingův stroj je uspořádaná šestice M = (Q, E, t, ô, q0, F), kde • Q je konečná neprázdná množina stavů, • E je konečná neprázdná vstupní abeceda (symboly, ze kterých se může skládat vstupní slovo), E C r, Kapitola 3 Jazyky typu 0 45 • ľ je konečná neprázdná pásková abeceda (symboly, které se mohou vyskytovat na pásce), • % ^ Q je počáteční stav, • F C Q je množina koncových stavů, • ô je přechodová funkce: ó: QxT ->■ QxTx {-1,0,1}, jinak S{qi,a) (gi;6,P), q,nqj EQ, a,beT, P e {-1,0,1} Podle definice ó funkce můžeme odvodit činnost Turingova stroje - v každém kroku, kdy je použito 5(qi, a) —► (qj,b,P), q,hqj E Q, a, b E T, P E { —1, 0,1}, jsou provedeny následující akce: • jsme ve stavu q{ a na pásce čtecí a zápisová hlava právě ukazuje na políčko označené a, • přejdeme do stavu qj, • symbol a na pásce přepíšeme symbolem b, • posuneme čtecí a zápisovou hlavu podle předpisu P. Takto definovaný Turingův stroj je deterministický Prázdná políčka pásky se obvykle označují symbolem U (nebo písmenem B, Blank), slovo je od prázdných políček odděleno (tedy obklopeno) symboly $, tyto symboly v přechodové funkci pomáhají zjistit, zda jsme na začátku či konci slova. Je možné stanovit také dva různé symboly - jeden pro vymezení začátku a druhý pro vymezení konce slova (například $ a #). Hraniční symbol (-y) je také součástí páskové abecedy. Množina F koncových stavů bývá často tvořena dvěma stavy, jedním pro přijetí a jedním pro odmítnutí slova: F = {qaCcept, qreject}, případně místo qreject je někdy pOUŽitO qerror- Definice 3.6 (Konfigurace Turingova stroje) Konfigurace Turingova stroje M, kde M = (Q, E, ľ, ô, q0, F), je (wi, q, w2), kde wi E T je část pásky před čtecí a zápisovou hlavou, q E Q je stav, ve kterém se řídicí jednotka nachází a w2 E T je část pásky za čtecí a zápisovou hlavou, čtecí a zápisová hlava ukazuje na první symbol řetězce w2. Počáteční konfigurace je (e,q0,w0) nebo ($,q0,w0$) (pokud chceme zahrnout do konfigurace i hraniční symboly), w0 E E je vstupní slovo, které má být zpracováno. Koncová konfigurace je (wi,qf,w2) (resp. ($wi,qf,w2$)), qf E F, wi,w2 E T*. Kapitola 3 Jazyky typu 0 46 Příklad 3.3 - Například konfigurace (abbca, q, daab) znamená, že se stroj nachází ve stavu q, na pásce je slovo abbcadaab a čtecí a zápisová hlava ukazuje na šestý symbol slova - d. Definice 3.7 (Relace přechodu mezi konfiguracemi) Relace přechodu mezi konfiguracemi je určena takto: (a,qi,a(3) h (ab,qj,f3) O 5(qhá) = (qj,b,l) (3.1) (a,qi,a(3) h (a,qj,bf3) O 5(qhá) = (qj,b,0) (3.2) (ac,qi,a(3) \-(a,qj,cb(3) ô(qi, a) = (qj} b,-1) (3.3) V prvním případě se čtecí a zápisová hlava posunuje doprava, v druhém zůstává na místě (tj. v dalším kroku bude číst totéž políčko jako v tomto) a v třetím případě se posunuje doleva. Příklad 3.4 - Sestrojíme Turingův stroj rozpoznávající jazyk L2 = {anbncn \ n > 0} M = ({q0,qP,qA,qB,qc,qf,qaccept}, {a,b, c}, {a, ä, b, b, c, č, U, $}, ô, {qaCcept}) Budeme postupovat takto: označíme první a (tj. přepíšeme symbolem ä), najdeme první b, označíme ho, pak najdeme první c, taktéž označíme, potom přejdeme na začátek (postupujeme doleva, dokud nenajdeme nejbližší označené ä), posuneme se o políčko dále na první neoznačené a, označíme ho, atd. Jednotlivé stavy znamenají: • qA - označili jsme a, přeskakujeme symboly a, b, hledáme první neoznačené b, • qs~ označili jsme b, přeskakujeme symboly b, č, hledáme první neoznačené c, • qc - označili jsme c, vracíme se na začátek k poslednímu označenému ä, při pohybu doleva přeskakujeme všechny symboly č, b, b, a. Definujeme ó funkci: S(qo, $) = (qaccept, 0) (přijali jsme prázdné slovo) %o, a) = (qA,a,i) S(qB,b) = (qB,b,l) ô(qc,a) = (qp,a,i) 6(qP a) = (QA,ä,l) 5(qB,č) = (qB,č,l) 5(qo,b) = (qf,b~A) 5(qA a) = (qA,a,l) 5(qB,c) = (qc,č,-l) S(qf,b) = (qf,b~A) 5(qA b) = (QA,b,l) 5(qc,X) = (qc,X,-l), 5(qf,č) = (qf,č,i) 5(qA b) = (QB,b,l) X G {a, b, b, č} 5(qf,$) = (qaccept, $j 0) Kapitola 3 Jazyky typu 0 47 Ukázka zpracování slova abc: (e,q0,abc) h (ä,qA,bc) h (äb,qB,c) h (ä,qc,bč) h (e,qc,äbč) h (ä,q0,bč) h h (äb,qf,č) h (äbč,qf,e) h (äbč, qaccept, e) Jestliže zaznamenáme i hraniční symboly, zpracování bude vypadat takto: ($,q0,abc$) h ($ä, g^&cS) h ($ä&, gB,c$) h ($ä,gc,6č$) h ($,gc,ä6č$) h h ($ä, g0, h ($äb, qf, č$) h ($ä&č, qf, $) h ($ä&č, qaccept, $) Ukázka zpracování slova aabbcc: (e,qo,aabbcc) h (ä,qA,abbcc) h (äa,qA,bbcc) h (äab,qB,bcc) h (äabb,qB,cc) h h (äa&, gc, 6čc) h (äa, g^, 66čc) h (ä, g^, abbčc) h (e, g^, äabbčc) h (ä, g0, abbčc) h h (ää, g^, 66čc) h (ää&, g^, 6čc) h (ääbb, g#, čc) h (ääbbč, g#, c) h (ääbb, qc, čč) h h (ääb,qc,bčč) h (ää, qc,bbčč) h (ä,qc,äbbčč) h (ää,qo,bbčč) h (ääb,qf,bčč) h h (ääbb,qf,čč) h (ääbbč,qf, č) h (ääbbčč,qf,e) h (ääbbčč, qaccept, e) Ukázka zpracování slova ac: (e, g0, ac) h (ä, g^, c) chyba =>- slovo ac není přijato. Ukázka zpracování slova e: (£,go,-s) h (e, qaCcept, z) Poznámka: Všimněme si rozdílu mezi činností Turingova stroje a dříve definovaných automatů: • Turingův stroj nejen čte vstupní pásku, může ji i zapisovat, • čtecí a zápisová hlava se může (nemusí) pohybovat různými směry, nejen doprava, • nepotřebujeme zásobník, ale přesto můžeme uchovávat i jinou informaci než označení stavu, ve kterém právě jsme - kamkoliv na pásku si můžeme cokoliv poznamenat a později tuto informaci využít, • na Turingově stroji lze provádět i výpočty. Turingovými stroji se budeme podrobněji zabývat v navazujícím kurzu Teorie vyčíslitelnosti. Kapitola 3 Jazyky typu 0 48 3.2.3 Varianty Turingova stroje Řekli jsme si, že Turingův stroj je v základní definici deterministický. Proto varianty můžeme především rozdělit podle tohoto kritéria: • deterministický - základní varianta, • nedeterministický - pro tentýž stav a obsah pásky lze definovat více různých akcí. Podobně, jako zásobníkový automat může mít více zásobníků, Turingův stroj může mít více pásek: • jednopáskový - základní varianta, • vícepáskový - máme více pásek, každá má vlastní čtecí a zápisovou hlavu, tyto hlavy se mohou pohybovat navzájem nezávisle (například první doprava, druhá doleva a třetí třeba zůstane na místě v tomtéž kroku zpracování). Na jedné pásce může být i více stop (podobně jako na paměťových médiích, třeba zálohovacích páskách): • jednostopý - na (každé) pásce je jen jedna stopa, • vícestopý - na pásce může být více stop, ale narozdíl od vícepáskového automatu zde všechny stopy téže pásky mají společnou čtecí a zápisovou hlavu. Dále můžeme stanovit možnost pohybu čtecí a zápisové hlavy: • možnost pohybu {—1,0,1} - čtecí a zápisová hlava se může pohybovat doleva nebo doprava, a nebo zůstat na místě, • možnost pohybu {—1,1}- čtecí a zápisová hlava se musí pohybovat v každém kroku, a to doleva nebo doprava, nesmí zůstat na místě. Páska může být • jednostranně nekonečná - vstupní slovo je na začátku výpočtu umístěno na začátek pásky, před ně již není možné nic napsat, • oboustranně nekonečná - základní varianta. Lze dokázat, že všechny výše uvedené varianty jsou navzájem ekvivalentní, všechny varianty lze převést na základní variantu - deterministický jednopáskový jednostopý automat, jehož čtecí a zápisová hlava se může pohybovat oběma směry nebo zůstat na místě a lze zapisovat i před vstupní slovo. Kapitola 3 Jazyky typu 0 49 3.3 Vztah Turingových strojů k jazykům typu 0 Zde ukážeme, že jazyky rozpoznávané Turingovým strojem jsou právě jazyky typu 0. Pro tuto vlastnost se také jazykům typu 0 říká rekurzívně spočetné jazyky, protože Turingův stroj vlastně pracuje na principu rekurze. Definice 3.8 (Rekurzívně spočetný jazyk) Jazyk nazveme rekurzívně spočetný (rekurzívně vyčíslitelný, částečně rekurzivní), pokud je přijímán nějakým Turingovým strojem (tento Turingův stroj se na slovo patřící do jazyka zastaví v akceptujícím stavu, na slovo nepatřící do jazyka se bud'zastaví v odmítajícím stavu nebo se dostane do nekonečné smyčky). Definice 3.9 (Rekurzívní jazyk) Jazyk nazveme rekurzívní, pokud je rozhodován nějakým Turingovým strojem (tento Turingův stroj se pro jakékoliv slovo zastaví, a to na slovo jazyka v akceptujícím stavu a na slovo nepatřící do jazyka v odmítajícím stavu, pro žádný vstup nepřejde do nekonečné smyčky). Veta 3.2 Ke každé gramatice G typu 0 lze sestrojí Turingův stroj M takový, že platí L(M) = L(G). Důkaz: Podle gramatiky G = (N, T, P, S) sestrojíme nedeterministický dvoustopý Turingův stroj M = (Q, E, ľ, ô, q0, F). První stopa obsahuje vstupní slovo, nemění se, slouží pro kontrolu, druhá stopa simuluje derivaci v gramatice, obsahuje větnou formu, u které v derivaci právě jsme (na začátku to je S). 1. Nedeterministicky zvolíme některé pravidlo a —► (3 v gramatice. 2. Pokud se a nachází ve větné formě, zvolíme některý výskyt a a přepíšeme ho na (3; pokud \f3\ ý nejdřív vhodně posuneme všechny symboly za řetězcem a doleva nebo doprava. 3. Porovnáme vstup na první stopě s obsahem druhé stopy - pokud je stejný, vstup přijmeme, jinak zpět k bodu 1. Dále v důkazu nebudeme pokračovat, postup si ukážeme na příkladu. □ Příklad 3.5 - Vytvoříme gramatiku typu 0 pro jazyk Kapitola 3 Jazyky typu 0 50 L19 = L2- {e} = {anbncn | n > 1} Gramatika: G = ({S, A, B, X}, {a, b, c}, P, S"), kde v P jsou pravidla S ->■ aAbX Ab^bA AX ->■ BXc AX ^ c bB ->■ 56 a5 —► aaA6 Ukázka odvození: S =>■ aA&X =>■ a6AX =>■ abBXc =>■ aBbXc =>■ aaA66Xc =>■ aa6A6Xc =>■ aa66AXc =>■ ^> aabbcc Podle této gramatiky sestrojíme Turingův stroj. Význam jednotlivých stavů: • go- • • nedeterministicky vybereme pravidlo, • qi, q2,...,qQ... vybrali jsme 1., 2., ..., 6. pravidlo, teď nedeterministicky vybereme, kde ho chceme použít, • qn... už jsme si vybrali místo pro uplatnění prvního pravidla, zpracovali jsme první symbol pravidla (první znak a přepíšeme na první znak (3), • q\2- ■ ■ přepisujeme druhý symbol pravidla ... • q2i- ■ .už jsme si vybrali místo pro uplatnění druhého pravidla, zpracovali jsme první symbol pravidla • qz- ■ ■ přepsali jsme celé pravidlo, vracíme se na začátek větné formy, bude další pravidlo, • qx- ■ ■ kontrola, jestli máme skončit, • q,jN• ■ ■ ještě ne (ještě neskončit, stopy mají různý obsah). Postup si nejdřív ukážeme na průběhu výpočtu slova, které bylo v gramatice pro ukázku odvozeno. Na průběhu výpočtu vidíme, že horní stopa se nemění, zatímco na dolní probíhá simulace generování tohoto slova v gramatice. S $ u U U u u a a b b S $ U U U U U a a b b Kapitola 3 Jazyky typu 0 51 Ta abbcc$\^f$aa b b c c T ' * a'511' $ U U U U uj \$ a A '?12' U U U U U ' a a 6 bcc$\^f$aabb c c T ' * a A b'gi3' U U U uj $ a A 6 X '?14' U U U ' a a 6 6cc$\^/$aa 6 6 c c ., ' mai6'fe'l$Uuj v$aA'^'6A"$Uu' l_ i - aa66cc$\^ h í ^ aabbccr Definujeme ó funkci - pro každé U G E U {□}, ľ e ľ: Nedeterministicky vybereme pravidlo gramatiky, které budeme uplatňovat na obsah druhé stopy: u\ (f U \ f U \ f U \ f u 5 I 9o, I = S I 9i, ,0 I , I 92, ,0 I , I g3, ,0 I I g6, 0 Zpracování prvního pravidla - nejdřív nedeterministicky vybereme, na kterém místě řetězce pravidlo uplatníme, a pak pro a —► (3 začneme přepisovat a na (3: 5UlUs)={(qiUsA\qilUaA s\qi,uMy^,uM,iiM^s S I 911, Uy^j = ^9l2, UA , 1J 5 ^9l2, ^ J = ^13, ^ , 1 ó I 9i3, y j = ^9u, ^ , l^j 5 ^9i4, y 1 = (iz, ^ , -1 ^ ( 9z, ^ j = í Qz, ^ , — 1 ) , V Ý $ (jdeme na začátek větné formy) ô [ qz, I = 9a:, ^ , 1 (jsme na začátku) Kapitola 3 Jazyky typu 0 52 S [ qK, ^ j = l^x, ^-'^1 (kontrolujeme, jestli už jsme na konci odvození slova ^ $ \ (obě stopy mají stejný obsah =>- konec odvození, konec S\QK^ l = l^r°Jpráce) u\ í U i\ v U není konec, přejdeme na začátek \Qk, y J \<1jn, y, J , pásky a zvolíme další pravidlo) 5 ( qjN, y^j = (^JN' y ' _1 1 S\ QjN' * ) = I ?0> * > 1 ^ I 92, ^ ] = \ í Q2, ^ , 1 ] , í souvání věděli, kde máme začít psát Funkce pro posun následujícího řetězce o 1 políčko doprava: ^ ( 9p, ^ ^ = ^9p, ^ , l^j , V ^ $ (nejdřív se přesuneme na konec řetězce) ô I 9p, í[ j = ^9p$, ^ , 1 5 ( 9pm, ^ j = Lpz, UM,-l ) , M G {a, 6, c, S, A, B, X, $} Kapitola 3 Jazyky typu 0 53 ll\ f U ^ \ (zapamatujeme si M, předchozí částí ô fce ho pak qFZ' M J l ^PM' j^-' I zkopírujeme vpravo) C/ \ | f/ A (zarážka 3 znamená, že jsme při uplatňování 3. pra-PZ' 3/ \ 31 -B ' i vidia gramatiky posunuli vše za tímto místem o 1 políčko doprava, teď můžeme zapsat pravou stranu pravidla, už se vejde) S | 93i, y j = ^932, Ux , 1 j ^ ^32, ^ j = (^lz, Uc , -1 t/ \ í Prav^^° gramatiky vyžaduje posun o 2 políčka, musíme funkci pro posun volat 2x) ^ | 962, y J = ^963, ^ , 1J ^ ^963, ^ J = ^ , "I Čtvrté pravidlo gramatiky vyžaduje posun následujících symbolů doleva (/? je kratší než a): ^ | 94, ^ J = ^41, ^ ,1 ^ ( 94i, ^ ^ = ^Qr, ^ , 1 ) (kontrolujeme, zda je ve slově přítomna celá a) Funkce pro posun následujícího řetězce o 1 políčko doleva: S | 9i?, ^ j = ^9w, ^ , 1 j ^ ^9w, ^ j = (^Ird, ^ , 1 S | 9i?D, ^ j = (qR, ^ , 1 j í ^9i?D, ^ j = ^9i?z, ^ , -1 ô | 9i?z, ^ j = [qRZ, ^ , -1 j ô [qRZ, 4 j = ^ ' _1 Pokud by /? byla delší než 1 znak, museli bychom pro zpracování celého pravidla použít stavy 942,943, • • • atd. pro další pravidla gramatiky Kapitola 3 Jazyky typu 0 54 Veta 3.3 Ke každému Turingovu stroji M lze sestrojit gramatiku G typu 0 takovou, že L (M) = L (G). Důkaz: Budeme postupovat takto: • vygenerujeme dvě kopie téhož slova, • první (horní) na konci generování použijeme jako výstup gramatiky, na druhé (spodní) budeme simulovat činnost TS, • výstup gramatiky bude složen pouze z terminálních symbolů jen tehdy, pokud simulace na druhé kopii skončí ve stavu qaCcePt- Neterminály máme několika typů: • neterminály ve tvaru sloupcového vektoru, jehož horní prvek G T nebo je e, • neterminály pro stav (zač. q0) a začátek a konec řetězce $, • další neterminály bez přímého vztahu k TS (S, S'). Pro lepší představu se podíváme na fragment ukázky odvození: S e a a b b c c $ a a b b c c aabbcc Postupně vytvoříme pravidla gramatiky. 1. Vygenerujeme dvě kopie téhož slova: S S' S' pro každé a G S S' S' -»• $ 2. Simulujeme činnost Turingova stroje: (a) pro ô(qi, a) = (qj, b, 1), a, b E T, q,h qj G Q vytvoříme pravidlo x x —> b Qj, pro a Kapitola 3 Jazyky typu 0 55 (b) pro ô(qi, a) = (qj, b, 0), a, b e T, q,,, qj G Q vytvoříme pravidlo , pro x G S U {e} (c) pro ô(qi, a) = (qj, b, — 1), a, b E T, q{, qj G Q vytvoříme pravidlo x x Qj b a íl y x c b , pro x, y E T, U {e}, c G ľ (d) proô(qí, U) = (qj, b, l),příp. ô(qh %) = (qj, b, l),b G T, qh qj G Q vytvoříme q$ qfi (e) pro5(gi;U) = (qJ7 b, 0),príp. ô(qi, $) = (qJ7b, 0),b G T, q,t,qj G Q vytvoříme qS q j y y e qS q j c c b (f) pro ó(q,t,U) = (qj,b,-l), příp. ó(q,t,$) = (ty, 6,-1), & G T, q,t,qj G Q vytvoříme pravidlo B, pro y G S U {e}, c G T 3. Zakončíme derivaci (vytvoří se terminálni slovo): (a) Posuneme qaCcept na začátek větné formy: Mqaccept -»■ qacceptM pro všechny neterminály M e N (b) Tvoříme terminály: a qaccept X d qaccept (c) Mažeme vše, co nevytvoří terminál: qaccept X qaccept (d) Konec derivace: gaccePt$ —► £ □ /3, kde \a\ < \/3\, a G (N U T)*N(N U T)*, (3 G (N U T)* Je přípustné také pravidlo S —► e, pokud e je slovo jazyka, který gramatika generuje, S se nesmí vyskytovat na pravé straně žádného pravidla. Definice 4.2 (Kontextová gramatika) Kontextová gramatika je gramatika s pravidly ve tvaru aA/3 ->■ «7/3, kde \^\ > 0, a, j3,7 G {N U T)* Je přípustné také pravidlo S —► e, pokud e je slovo jazyka, který gramatika generuje, S se nesmí vyskytovat na pravé straně žádného pravidla. 56 Kapitola 4 Jazyky typu 1 57 Je zřejmé, že každá kontextová gramatika je zároveň nezkracující, vyplývá to přímo z tvaru pravidel. Platí však i opačná relace? Veta 4.1 Ke každé nezkracující gramatice G lze sestrojit kontextovou gramatiku G' takovou, že L(G') = L (G). Důkaz: Každé pravidlo typu A1A2... Am —► BiB2 ■ ■ ■ Bn, které nemá kontextový tvar, nahradíme množinou pravidel: Al A2 A3 A —> • • • Ci ^2 ^3 Ci A2 A3 A —> Ci c2 ^3 C\ c2 A3 A —> Ci c2 c3 Ci c2... Gm- -1 A C\ C2... Cm-i G m Bm 4-1 • B n Ci c2... r -1 r Bm+i ■ ■ ■ Bn —► Ci. n • • ^m—l ...B Ci c2... r -1 Bm+i... Bn —► Ci i 5m ... j C\ B2 ... Bn —► Bi ... B Kde Ci jsou nově přidané neterminály, které se jinde nevyskytují. □ Příklad 4.1 - Vytvoříme nezkracující gramatiku pro jazyk L5 = {ww \ w E {a, b}*} S —► XZaZa I XZbZb I aa \ bb \ e pokud w končí na a, začínáme prvním pravidlem - ... Za ... Za pokud w končí na b, začínáme druhým pravidlem - ... Zb... Zb XZa aZaXa | bZaXb | aaXa \ baXb v první polovině jsme vygenerovali a, pošleme info do druhé - ... aZaXa ... Za v první polovině jsme vygenerovali b, pošleme info do druhé - ... bZaXb... Za Xaa —► aXa symbol Xa nebo Xb posíláme doprava Xab -+ bXa Xb(i —> (iXb Xbb -+ bXb Kapitola 4 Jazyky typu 1 58 XaZa —► YaZa | aa info doputovalo k zarážce na konci slova - ... aZa ... YaZa XbZa^YbZa\ba ...bZa...YbZa aY —► Ya symbol Y posíláme doleva - zpráva „pokračuj v první polovině" bY ->■ Yb ZaY —► XZa překročili jsme zarážku na konci první poloviny slova Dále totéž pro Zb místo Za: XZb —► aZbXa | bZbXb | abXa \ bbXb XaZb —► YaZb | ab XbZb ->■ YbZb | 66 z^y —► xzb Ukázka odvození: S XZaZa aZaXaZa aZaFaZa aXZaaZa abZaXbaZa =>- abZaaXbZa =>- abZaaYbZa =>- abZaYabZa =>- abXZaabZa =>- abbXbabZa =>- =>- abbaXbbZa =>- abbabXbZa =>- abbabba 4.2 Kurodova normální forma pro gramatiky typu 1 (Kuroda normál form, KNF) Definice 4.3 (Kurodova normální forma pro gramatiky typu 1) Gramatika jev KNF, jestliže všechna její pravidla jsou ve tvaru A ^ BC AB -»■ CD A a A,B,C,D e N,a e T, případně S ^ e Veta 4.2 Ke feždé nezkracující (i kontextové) gramatice G lze sestrojit gramatiku G' v Ku-rodově normální formě takovou, že L(G') = L(G). Důkaz: Budeme postupovat takto: Kapitola 4 Jazyky typu 1 59 • pravidla v bezkontextovétn tvaru: použijeme algoritmus pro převod na Chom-ského NR • pravidla, která nejsou bezkontextového typu: upravíme pravidla podle následujícího algoritmu. Vstup: nezkracující gramatika bez jednoduchých pravidel typu X —► y, X,Y e N 1. Pro všechna pravidla: • všechny terminály (na levé i pravé straně pravidla) a E T nahradíme „pomocnými" neterminály Na, • pro všechny neterminály vytvořené v předchozím bodu přidáme pravidlo Na —► a. 2. Pravidla A —► BiB2 ... Bn, n > 2 nahradíme pravidly A ->■ BxXx Xi —► B2X2 Xn-2 —► Bn-\Bn 3. Pravidla A\A2... Am —► B\B2... Bm, m > 2 nahradíme pravidly AXA2 ExXx X\A3 —> B2X2 Xm—2Am > Bm_\Bm 4. Nezkracující pravidla A\A2... Am —► B\B2 ... Bn, 2 < m < n nahradíme pravidly A\A2 —► B\X\ Xm_i —► BmXm X1A3 —► B2X2 Xm —► Bm+iXm+i Xm—2Am > Bm_\Xm_\ Xn_2 > Bn_\Bn □ Kapitola 4 Jazyky typu 1 60 4.3 Lineárne ohraničený automat Tak jako jazykům typu 0 můžeme přiřadit Turingův stroj a například konečný automat rozpoznává právě regulární jazyky, k jazykům typu 1 můžeme přiřadit lineárně ohraničený automat (LOA, Lineary Bounded Automaton). Definici LOA přejímáme z definice TS, jen přidáváme zákaz přepisu hraničních symbolů. Definice 4.4 (Lineárně ohraničený automat) Lineárně ohraničený automat je jedno-páskový (nedeterministický) Turingův stroj M = (Q, E, ľ, ô, q0, F), ve kterém čtecí a zápisová hlava nesmí během výpočtu přepsat hraniční symboly $ pásky (tj. slovo nesmí být během výpočtu prodlužováno). Definice 4.5 (Konfigurace lineárně ohraničeného automatu) Konfigurace lineárně ohraničeného automatu je (a, q, f3), kde q je stav, na pásce je řetězec a/3, čtecí a zápisová hlava ukazuje na první symbol řetězce f3. Přechod mezi konfiguracemi je definován stejně jako u Turingova stroje, jen je třeba zohlednit nemožnost přepisu hraničních symbolů. Veta 4.3 Pro konkrétní lineárně ohraničený automat M a daný vstup w0 existuje konečný počet různých konfigurací. Důkaz: Protože máme konečný počet stavů, konečný počet páskových symbolů a omezenou část vstupní pásky, platí: jestliže označíme d ... délka používané části pásky, s ... počet stavů v Q, g ... počet prvků páskové abecedy ľ, pak počet všech možných různých konfigurací je d ■ s ■ gd (hlava může být na d různých pozicích, nabývá hodnot s různých stavů, počet všech možných řetězců nad abecedou ľ o délce d je gd). □ Poznámka: Rekurzívní jazyky jsme definovali v definici 3.9 na straně 49. Narozdíl od rekurzívně spočetných jazyků je lze zpracovat Turingovým strojem tak, že pro Kapitola 4 Jazyky typu 1 61 jakýkoliv vstup výpočet skončí přechodem do některého koncového stavu, bez přechodu do nekonečné smyčky, a výpočet probíhá na principu rekurze (rekurzívně uplatňujeme ô funkci). Důsledek 4.4 LOA lze vždy navrhnout tak, aby výpočet skončil nad jakýmkoliv vstupem. Proto jazyky, které jsou přijímány nejakým LOA, jsou pravé rekurzívní jazyky. Důkaz: Stačí při každém kroku výpočtu LOA zkontrolovat, jestli se nenachází v konfiguraci, ve které už byl dříve. Pokud ano, výpočet v původním automatu se dostal do smyčky a my můžeme skončit v chybovém stavu qreject (vstup nepřijmeme). Pokud pro každý vstup LOA najdeme počet políček pásky, se kterými během výpočtu bude pracovat čtecí a zápisová hlava (tj. délka části pásky použité při výpočtu, prostorová složitost výpočtu automatu nad daným vstupem), zjistíme, že tato hodnota je lineárně závislá na délce vstupu, tedy existuje přirozené číslo k takové, že délka použité části pásky je menší než k ■ \w\. Odtud je odvozen také název tohoto automatu - automat s lineárně ohraničeným pracovním prostorem. □ Poznámka: V některých zdrojích je LOA definován přímo jako Turingův stroj s lineárně ohraničeným pracovním prostorem, a je tedy dovoleno používat pro výpočet každého slova w nejvýše k ■ \w\ políček pásky (tedy nejen pro k = 1). Veta 4.5 Jazyky typu 1 jsou pravé jazyky přijímané lineárne ohraničenými automaty. Důkaz: („=>") Máme nezkracující gramatiku G, která generuje zadaný jazyk typu 1 L. Derivace v této gramatice je ve tvaru S =>• wi =>- w2 =>• ... wn, kde \wí\ < \wj\ pro i < j. Sestrojíme LOA M takto: 1. Na vstupu je slovo, o kterém chceme zjistit, zda je generováno gramatikou G. 2. Na tento vstup budeme uplatňovat pravidla gramatiky takto: (a) nedeterministicky zvolíme pravidlo gramatiky (a —► (3), Kapitola 4 Jazyky typu 1 62 (b) najdeme v řetězci na pásce některý výskyt pravé strany tohoto pravidla {(3) - pokud je těchto výskytů více, nedeterministicky mezi nimi jeden zvolíme, (c) výskyt (3 přepíšeme řetězcem a, pokud je a kratší, posuneme to, co následuje za (3, doleva, aby zbytek pracovního slova navazoval na a. 3. Výpočet ukončíme: • ve stavu akceptování (qaccept), pokud na pásce bude pouze startovací symbol gramatiky a nic jiného, • ve stavu odmítnutí slova (qreject, qerror), pokud je na pásce něco jiného a již nelze použít žádné pravidlo gramatiky Je zřejmé, že takto vytvořený LOA vytváří derivaci slova podle gramatiky G zprava doleva (a tedy konstruuje derivační strom pro toto slovo zdola nahoru ke kořeni stromu ohodnocenému startovacím symbolem) a ve stavu akceptování skončí právě na ta slova, která generuje gramatika G. □ Důkaz: („^=") Je dán LOA M.. Vytvoříme nezkracující gramatiku G podobně jako v obdobném důkazu pro Turingovy stroje a gramatiky typu 0, jen musíme pravidla upravit tak, aby byla nezkracující. 1. V gramatice G nejdřív vygenerujeme řetězec neterminálů, který představuje dvojici slov na vstupu simulovaného LOA. Oproti gramatice typu 0 musíme symboly pro začátek a konec pracovní části pásky a také symbol pro stav automatu umístit dovnitř neterminálů pro symboly slova, abychom nebyli nuceni na konci výpočtu použít epsilonová pravidla. S a S' e $, q0, a $, qo, $ S' a S' a a a, $ pro každé a G S Dostaneme řetězec neterminálů Cli a2 a3 $, qo, ai a2 a3 O-ki $ Kapitola 4 Jazyky typu 1 63 2. Simulujeme průběh výpočtu LOA: Např. pro každou část 5 funkce typu 5(qi, a) 3 (qj, b, 1) pro každé c e T — {$} Podobně pro ostatní směry pohybu čtecí a zápisové hlavy, navíc musíme ošetřit práci s neterminály, které obsahují hraniční znaky $. 3. Ukončení výpočtu: X y x y q,i,a c b _qj,c_ x y x y a b x $, a x K, a x K, a y —► X Qacci b r -, r y K, b x y K, b xy Posuneme qacc dopředu na začátek řetězce, pak přejdeme do ukončujícího stavu K a postupně všechny neterminály přepíšeme na terminály □ 4.4 Uzáverové vlastnosti jazyků typu 1 Věta 4.6 Třída jazyků typu 1 je uzavřena vzhledem k operacím sjednocení, zřetězení, iterace, pozitivní iterace, homomorfismu, substituce. Důkaz: Stejně jako u bezkontextových jazyků, pomocí gramatik. Například pro sjednocení přidáme navíc pravidlo S —► Si | S2, kde S je nově přidaný symbol, Si je startovací symbol první gramatiky a S2 je startovací symbol druhé gramatiky. □ Věta 4.7 Třída jazyků typu 1 je uzavřena vzhledem k operaci průniku. Kapitola 4 Jazyky typu 1 64 Důkaz: Máme dva LOA Mi, M2. Sestrojíme LOA M, který bude postupně simulovat výpočet obou těchto automatů, a pokud oba skončí s akceptováním vstupního slova, toto slovo také akceptuje. 1. Na vstupní pásce pro akceptování slova w bude řetězec $w#w$. 2. Nejdřív M simuluje na první kopii slova w výpočet stroje M i s tím, že hraniční symboly jsou $ a #. 3. Pokud simulovaný výpočet skončí ve stavu akceptování slova, posune čtecí a zápisovou hlavu na první symbol za znakem # (tj. na první symbol druhé kopie slova w) a simuluje výpočet stroje M2. 4. Pokud tento výpočet skončí ve stavu akceptování, M akceptuje slovo w. □ Věta 4.8 Třída jazyků typu 1 je uzavřena vzhledem k operaci doplňku. Důkaz lze provést pomocí DeMorganových pravidel nebo konstrukčně. Důkaz pomocí DeMorganových pravidel můžeme nechat na čtenáři, konstrukční důkaz je jednoduchý: Důkaz: LOA lze vždy sestrojit tak, aby jeho výpočet byl konečný. Proto aby přijímal doplněk původního jazyka, pouze zaměníme akceptující a chybový stav. □ 1} Množinu všech OL-systémů budeme označovat zkratkou OL, tedy fakt, že g0 je OL-systém, můžeme napsat jako g0 E OL. Třídu (množinu) jazyků generovaných OL-systémy značíme Jšr(OL), jak je v těchto skriptech pro třídy jazyků zvykem, a tedy fakt, že jazyk L2o patří do této třídy, lze zapsat jako L2o £ =žf (OL). Veta 5.1 Jazyk L2± = {a, aa} nelze generovat žádným OL-systémem, tedy L21 ^ Jšŕ(OL). Důkaz: Předpokládejme, že existuje OL-systém g0 = (ľ,P,uj0) generující jazyk L2\. Pak axiomem ujq musí být některé ze slov jazyka (protože máme jen jednu abecedu E). Když zvolíme jako axiom řetězec a, musíme mít možnost vygenerovat řetězec aa, tedy musí existovat derivace a =^*Go aa- To ale znamená, že lze symbol a zdvojit, a proto by do jazyka musely patřit i řetězce aaaa, aaaaaaaa, ...=>• axiomem nemůže být řetězec a. Když zvolíme j ako axiom řetězec aa, musíme mít možnost vygenerovat řetězec a, tedy musí existovat derivace aa =^q0 a. To ale znamená, že musí existovat možnosti derivace a ^*Go a a proto by do jazyka musel patřit i řetězec e, tedy axiomem nemůže být řetězec aa. Axiom musí vždy patřit do jazyka, tedy nenašli jsme OL-systém, který by generoval tento jazyk, L21 £ Jšŕ(OL). □ Důsledek 5.2 Generativní síla OL-systémů je neporovnatelná s generativní sílou bezkon-textových gramatik, i když používá stejný typ pravidel - existují bezkontextové jazyky, které nepatří do třídy Jšŕ(OL) a existují jazyky generované OL-systémy, které nejsou bezkontextové. Proto paralelní způsob práce zásadně mění vlastnosti gramatik. Kapitola 5 L-systémy 69 Zapisujeme Jŕ(0L) (© Jŕ(CF) (5.1) OL-systémy mají některé zajímavé vlastnosti týkající se výpočtů - v příkladu do těchto vlastností trochu nahlédneme: Příklad 5.3 - Gp = ({a, b}, {a —► ab, b —► a}, b) Ukázka odvození: b =^gf a =^Gf ab abď =^Gf abacib =^gf obaabába =^gf abaababaabaab =^gf ■ ■ ■ Pro délky slov platí: l^o 1^2 1^3 1^5 1 1 2 3 5 8 13 Prvky derivace jsou řetězce s délkou Fibbonacciho čísel, tedy + = \idi+2\ , i > 0. 5.3 EOL-systémy EOL-systém má oproti OL-systému navíc terminálni abecedu A C V. Do jazyka generovaného EOL-systémem řadíme pouze ty členy derivací, které se skládají jen z terminálních symbolů. Terminálni slovo se může dále vyvíjet, součástí jedné derivace bývá i více terminálních slov. Z biologického hlediska lze roli terminálni abecedy chápat jako filtr vybírající pouze ty stavy prostředí, které nás z nějakého důvodu zajímají - členy derivace, které obsahují pouze prvky terminálni abecedy, patří do jazyka generovaného systémem, kdežto ty členy derivace, které obsahují nejméně jeden symbol nepatřící do terminálni abecedy, do jazyka generovaného systémem nepatří. Kapitola 5 L-systémy 70 Definice 5.4 (EOL-schéma) EOL-schéma je definováno jako SE = (V, A, P), kde • V je neprázdná konečná abeceda systému, • A je neprázdná terminálni abeceda systému, A C V, • P je množina pravidel bezkontextového typu P C V x V*. Definice 5.5 (EOL-systém) EOL-systém je definován jako GE = (V, A, P, lo0), kde • (V, A, P) je EOL-schéma, • lo0 je axiom (startovací slovo). Krok odvození je stejně určen jako u OL-systémů. Definice 5.6 (Jazyk EOL-systému) Jazyk generovaný EOL-systémem GE určeným jako GE = (V,A,P,uj0)je L(GE) = {w E A* | uj0 ^* w}. Příklad 5.4 - Následující EOL-systém GE generuje jazyk L19 = L2 - {e} = {anbncn | n > 1} Stejně jako v příkladu 5.1 jde o jazyk, který není bezkontextový. GE = (V, A, P, lo0), kde V = {A, B, C, A', B', C', F, a, b, c}, A = {a, b, c}, uj0 = ABC, množina P obsahuje tato vývojová pravidla: A - ■* AA! a A' - -> A' a a - ->■ F F - -> F B - ->■ BB' b B1 - -+ B1 b b - ■» F C - -+ CG' c C1 - -> C1 c c - F Ukázka dvou derivací, z nichž jen první vygeneruje terminálni slovo: ABC ^Ge AA'BB'CC ^Ge AA'A'B B'B'C C'C ^Ge aaabbbccc ^Ge F6 ^Ge ... ABC ^Ge AA'BB'CC' ^Ge AA'aBB'B'CC'C' ^Ge aaFbbbccc ^Ge ^ge fffffffff ^ge... V druhé derivaci se nikdy nedostaneme ke slovu, které se skládá pouze z termi-nálních symbolů, tedy ke slovům jazyka generovaného tímto systémem se dostaneme jen tak, že pravidla generující některý terminálni symbol (a, b, c) použijeme pro všechny symboly v přepisovaném slově zároveň. Symbol F zde slouží pro synchronizaci generování terminálních symbolů a, b, c tak, aby jich byl ve slově vždy stejný počet. Kapitola 5 L-systémy 71 Veta 5.3 EOL-systétny jsou silnější než bezkontextové gramatiky, tj. Jŕ{CF) C Jŕ(EOL) (5.2) Důkaz: Algoritmus vytvoření EOL-systému ekvivalentního k zadané bezkontextové gramatice zde nebudeme přesně probírat, ale čtenář si ho jistě sám celý domyslí s malou nápovědou - každou sadu pravidel pro stejný neterminál A —► «i | «2 | ... v bezkontextové gramatice nahradíme sadou pravidel v EOL-systému A —► A | «i | «2 | • • •/ čímž zajistíme možnost „sekvenčního" odvození i při použití paralelismu. Například jazyk generovaný EOL-systémem v příkladu 5.4 není bezkontextový, platí Liq E áf(EOL) — áf(CF). Proto platí, že EOL-systémy jsou silnější než bezkontextové gramatiky, třebaže se od nich liší vlastně jen postupem derivování (paralelním). □ Příklad 5.5 - Ge = {{A, a}, {a}, {A —► a, A —► aa, a —► a}, A) Ukázky odvození: A ^ge a A ^Ge aa Generovaný jazyk je L/21 = {a, aa} Věta 5.4 EOL-systémy jsou silnější než OL-systémy, tedy platí (OL) C ^(EOL) (5.3) Důkaz: OL-systémy můžeme brát jako speciální případ EOL-systémů, kde A = V. Tím je dána relace Jž?(0L) C áf(EOL). Fakt, že jde o vlastní podmnožinu (tj. že existují jazyky generované EOL-systémy, které nelze generovat žádným OL-systémem), dokazuje jazyk L21 e Jŕ(EOL) - (OL). □ Kapitola 5 L-systémy 72 5.4 TOL-systémy TOL-systém získáme z OL-systému, když pravidla rozdělíme do tabulek a stanovíme, že v jednom kroku derivace se použijí pravidla z jediné vybrané tabulky TOL-systém je tedy určen abecedou, sadou tabulek T obsahujících pravidla (ta nahrazuje množinu pravidel P). Definice 5.7 (TOL-schéma) TOL-schéma je definováno jako ST = (V, T), kde • V je neprázdná konečná abeceda systému, • T je množina tabulek obsahujících pravidla bezkontextového typu P C V x V*. Definice 5.8 (TOL-systém) TOL-systém je definován jako GT = (V, T, lo0), kde • (V, T) je TOL-schéma, • lo0 je axiom (startovací slovo). Krok odvození značený =^gt se provádí následovně: • vybereme si některou tabulku z množiny tabulek T, • při odvození postupujeme stejně jako u OL-systému (tj. všechny symboly přepisujeme), použijeme však pouze pravidla z jediné vybrané tabulky Definice 5.9 (Jazyk TOL-systému) Jazyk generovaný TOL-systémem GE = (V,T,lo0) Příklad 5.6 - GT = ({a}, {T1;T2}, a), kde Ti = {a —► aa], T2 = {a —► e} Ukázka odvození: CL =^Gt ďďďď ^ (použili jsme dvakrát první tabulku, pak jednou druhou tabulku). Generujeme tento jazyk: L(GT) = {w e V* | lo0 ^*gt w}. Kapitola 5 L-systémy 73 Kdybychom shrnuli obě tabulky TOL-systému z příkladu 5.6 do jedné a vytvořili tak pouhý OL-systém, vygenerovaný jazyk by byl a*. Poznámka: Dá se dokázat, že L22 £ =žf (OL) (třebaže jazyk bez přidání e by pro OL-systém nebyl problém), protože axiom musí obsahovat alespoň jeden znak a tedy přidání prázdného slova do abecedy by vyžadovalo „zkracující" pravidlo a —► e, které by ovšem udělalo v odvození paseku - vznikl by jazyk a*. Veta 5.5 Ke každému OL-systému lze sestrojit TOL-systém, který generuje tentýž jazyk, navíc, TOL-systémy jsou silnejší než OL-systémy: (OL) C Jšŕ(TOL) (5.4) Důkaz: Postup převodu OL-systému na TOL-systém je jednoduchý - prostě všechna pravidla OL-systému shrneme do jediné tabulky, ta se použije v každém kroku odvození. Vlastní podmnožinu lze dokázat například pomocí jazyka L22 E Jšŕ(TOL) — Věta 5.6 Generativní síla TOL-systémů je neporovnatelná s generativní sílou bezkontexto-vých gramatik: Jšŕ(TOL) (© Jr{CF) (5.5) Důkaz: Do množiny Jšŕ(TOL) — Jr(CF) patří například jazyk L4 = {a2" n > OJ (v příkladu 5.1 na straně 67 je generován OL-systémem, a tedy je možno ho generovat i TOL-systémem). Do množiny áf(CF) — Jšŕ(TOL) zase můžeme zařadit jazyk Lx = {anbn | n > 1} (když počet znaků roste pomaleji než exponenciálně, potřebovali bychom e-pravidlo a —► e, a totéž i pro 6, třeba i v jiné tabulce než exponenciální pravidlo a —► aa; jenže když existuje e-pravidlo, pak se do jazyka dostane i prázdné slovo, což do L\ nepatří). □ Kapitola 5 L-systémy 74 5.5 ETOL-systémy ETOL-systémy jsou kombinace EOL a TOL-systémů, tedy máme terminálni abecedu a pravidla rozdělená do tabulek. Definici si čtenář může vytvořit sám z definic EOL-a TOL-systémů. Příklad 5.7 - GET = ({A,B,C,a,b,c}, {a,b,c}, {Ti,r2,r3}, ABC), kde Ti = {A —► Aa, 5 —► 56, C —► Cc, a —► a, 6^6, c —► c}, T2 = {A —► a, B —► 6, C —► c, a —► a, 6^6, c —► c} T3 = {A —► e, B —► e, C —► e, a —► e, 6 —► e, c —► Ukázka odvození: ABC =^get AaBbCc =^get AaaBbbCcc =^get aaabbbccc Generovaný jazyk je L2 = {anbncn | n > 0} Při generování jazyka L2 byly plně využity výhody ETOL-systému - oddělení terminálni abecedy pro růst délky slova, který není exponenciální, a rozdělení do tabulek pro synchronizaci délky všech tří částí slova a navíc pro vygenerování prázdného slova. Tento jazyk nelze vygenerovat žádným OL-systémem, EOL-systémem ani TOL-systémem. Důkazy následujících vztahů jsou poměrně jednoduché, proto je necháme na čtenáři (vlastně vyplývají z vlastností dříve definovaných jednodušších L-systémů): Existují i další varianty L-systémů včetně systémů pracujících s kontextem nebo stochastických L-systémů. Veta 5.7 (OL) C áf(ETOL) Jiŕ(EOL) C ^(ETOL) Jšŕ(TOL) C ^(ETOL) ££(CF) c Jŕ(ETOL) (5.6) (5.7) (5.8) (5.9) Kapitola 5 L-systémy 75 5.6 Možnosti využití L-systémů v grafice L-systémy se v praxi využívají především v grafice, kde slouží k modelování a generování tzv. fraktálu2. Používají se například ve filmovém průmyslu pro generování realistických „hromadných" výjevů, jako je například les stromů nebo oblaka na nebi. Aby tyto výjevy vypadaly realisticky, lze do jejich generování zanést i prvek náhody - tak vznikly stochastické L-systémy, kde je každému pravidlu přiřazeno číslo z intervalu od 0 do 1 určující pravděpodobnost použití tohoto pravidla, součet hodnot pravděpodobností pravidel se stejnou levou stranou musí být 1. Při grafické reprezentaci L-systémů symbol F určuje čáru o zadané délce, která se má vykreslit a symboly + a — znamenají pootočení doprava nebo doleva o zadaný úhel. Podle axiomu a pravidel se provede určitý počet odvození a výsledný řetězec (stav prostředí) se pak graficky interpretuje. Na obrázku 5.1 na straně 76 je ukázka několika jednoduchých fraktálu. Příklad 5.8 - Fraktál na obrázku 5.Id se nazývá Kochova vločka a byl vytvořen L-systémem s axiomem F + + F + + F a pravidlem F —► F — F + + F — F postupně čtyřmi průchody: F++F++F F-F++F-F++F-F++F-F++F-F++F-F ... (už třetí člen derivace se skládá ze 112 symbolů, tedy ho neuvádíme). To jsou ovšem jen jednoduché příklady. Existuje více různých způsobů jak do obrázku zapracovat barvy, náhodnost, kontext apod. Některé programy pro vytváření velmi působivých fraktálu můžeme najít také na internetu, stačí do vyhledávače zadat například řetězec L-systems nebo L-systémy 2Fraktál je soběpodobný útvar, který je velmi složitě tvarovaný a přesto je reprezentován velmi jednoduchou formou (třeba několika pravidly OL-systému). To, že je útvar soběpodobný, znamená, že detaily útvaru v různých rozlišeních jsou podobné útvaru celému. Kapitola 5 L-systémy 76 ABC D), m2 = (A ->■ aA, B ->■ B, C ->■ aC, D ->■ D), m3 = (A ->■ A, B ->■ bB, C ->■ C, D ->■ bD), 1714 = {A —► a, B b, C a, D —► b) Ukázka odvození: S =^m ABCD =^m aABaCD =^M aAbBaCbD =^M aAbbBaCbbD =^M aabbbaabbb V derivaci jsme použili nejdřív první matici, pak druhou, dvakrát za sebou třetí a nakonec čtvrtou, která ukončila derivaci. Generovaný jazyk není bezkontextový: L(GM) = L23 = {aiVaiV\i,j>l} Kapitola 6 Formální systémy 79 Příklad 6.2 - GM = ({S, A, B, C}, {a,b, c}, {mum2,m3}, S), kde m1 = (S ABC), m2 = (A^aA, B ->■ 65, C ->■ cC), ííi3 = (A —► a, B —► 6, C —► c) Ukázka odvození: S* =^m ABC =^m aAbBcC =^m aaAbbBccC =^m aaabbbccc Generovaný jazyk je L19 = {anbncn I n > 1} Veta 6.1 Maticové gramatiky jsou silnější než bezkontextové: Důkaz: Pro kteroukoliv bezkontextovou gramatiku sestrojíme maticovou gramatiku, která by generovala tentýž jazyk, velmi jednoduše - pro každé pravidlo bezkontextové gramatiky vytvoříme samostatnou (tedy jednoprvkovou) posloupnost, matice tedy bude obsahovat tolik posloupností, kolik měla původní gramatika pravidel. Takto vytvořená maticová gramatika přesně kopíruje sekvenční postup odvozování původní bezkontextové gramatiky. Vlastní podmnožina je zřejmá: L19 = {anbncn | n > 1} G ^(MAT) - ^(CF) (je 6.3 Gramatické systémy Dosud uvedené modely počítají s jedinou gramatikou vybavenou (vývojovými) pravidly, a s jediným slovem, které je zpracováváno pravidly gramatiky. Toto slovo můžeme považovat za prostředí, do kterého gramatika zasahuje svými pravidly. Tento jednoduchý model lze rozšířit na gramatický systém buď tak, že použijeme několik gramatik, které mají každá vlastní prostředí a mezi nimi probíhá určitá komunikace, a nebo tyto gramatiky necháme spolupracovat na společném prostředí a případně přidáme některé další vlastnosti. Komunikace pak může probíhat &(CF) C ^(MAT) (6.1) generován maticovou gramatikou v příkladu 6.2). □ Kapitola 6 Formální systémy 80 třeba přes prostředí. Činnost těchto gramatik bývá synchronizována univerzálními hodinami. První modely gramatických systémů se objevily už v roce 1978 a byly motivovány využitím v distribuované umělé inteligenci. Šlo o tzv. spolupracující (cooperating) gramatiky. Větších možností využití se dočkaly tzv. CD (Cooperated Distributed) gramatické systémy, které pracovaly metodou dnes například v sociálních vědách označovanou jako černá tabule (blackboard architecture for problem solving) - společné prostředí je jakousi tabulí, na kterou se „dívají" gramatiky a sledují, zda se na této tabuli neobjeví něco, co dokážou zpracovat svými pravidly. Podobné modely mají své praktické využití například v robotíce nebo při programování nezávislých softwarových agentů. Gramatickým systémem modelujeme chování robotů či agentů (představovaných gramatikami, pravidla jsou množina proveditelných akcí) pohybujících se ve společném prostředí, ať už softwarovém (operační systém či počítačová sít) nebo fyzicky reálném (místnost). V takovém případě někdy hovoříme o agentových systémech. 6.3.1 Kolonie Kolonie jsou velmi jednoduchý gramatický systém, který můžeme chápat jako společenství jednoduchých gramatik - komponent, které spolupracují na sdíleném prostředí. Všechny gramatiky sdružené v kolonii mají společnou abecedu a terminálni abecedu. Abeceda kolonie je množina symbolů, které se mohou vyskytovat v prostředí a se kterými tedy lze pracovat, terminálni abeceda (je podmnožinou abecedy kolonie) určuje symboly, ze kterých se mohou skládat terminálni slova, která pak řadíme do jazyka kolonie. Každá komponenta má svůj startovací symbol a jazyk. Startovací symbol je některý prvek abecedy kolonie (může patřit i do terminálni abecedy systému), určuje „objekt", se kterým komponenta dokáže pracovat. Jazyk komponenty je množina slov nad abecedou kolonie neobsahujících startovací symbol komponenty, je to jakási množina „akcí", které komponenta může s některým výskytem svého startovacího symbolu v prostředí provést. Činnost komponenty můžeme tedy chápat tak, že hledá v prostředí svůj startovací symbol, a pokud najde kterýkoliv jeho výskyt (případně nezabraný jinou Kapitola 6 Formální systémy 81 komponentou, pokud komponenty pracují paralelně), nahradí ho některým slovem svého jazyka. Komponenta sama o sobě je vlastně jednoduchá gramatika generující konečný jazyk (konečný proto, že startovací symbol komponenty se nesmí vyskytovat v jejím jazyce), lze ji přepsat na regulární gramatiku tak, že na levou stranu pravidel dáme startovací symbol komponenty a na pravou postupně všechna slova jejího jazyka. Prostředí je zpracováváno pouze komponentami. Může obsahovat jakýkoliv řetězec symbolů patřících do abecedy kolonie. Tento řetězec nazýváme stavem prostředí, počátečním stavem prostředí je axiom kolonie. Definice 6.2 (Kolonie) Kolonie je uspořádaná čtveřice C = (V, T, 1Z, lo0), kde • V je konečná neprázdná abeceda kolonie, • T neprázdná terminálni abeceda kolonie, T C V, • 1Z je konečná multimnožina1 komponent, 1Z = {(S,F) | S G V), F C (V — {S})*, F je konečná a neprázdná}, S je startovací symbol komponenty (S, F) a F je konečný jazyk této komponenty, • lo0 je axiom. Pro kolonie existuje hodně typů odvození, k základním řadíme tyto čtyři: • sekvenční mód (b, basic) - kolonie pracuje podobně jako gramatiky Chomského hierarchie, tedy v každém kroku odvození je náhodně vybrána jedna komponenta, která v prostředí zpracuje jediný výskyt svého startovacího symbolu (nahradí ho některým slovem svého jazyka), • sekvenčně-paralelní mód (t, terminal) - v každém kroku odvození je sekvenčně vybrána jediná komponenta, ta pak zpracuje všechny výskyty svého startovacího symbolu v prostředí, každý z nich nahradí některým ze slov svého jazyka (obecně každý výskyt svého startovacího symbolu může nahradit jiným slovem), • slabý paralelismus (wp, weakly parallel) - každá komponenta, která může pracovat, také musí pracovat, tedy když se v daném kroku odvození v prostředí 1Pro připomenutí: v multimnožině se narozdíl od množiny může vyskytovat i více stejných prvků, tedy v multimnožině komponent může existovat i více komponent stejně definovaných. Kapitola 6 Formální systémy 82 vyskytne startovací symbol komponenty a není zpracováván jinou komponentou, komponenta tento symbol musí zpracovat, • silný paralelismus (sp, strongly parallel) - podobně jako slabý paralelismus, jen navíc v případě, že komponenta by měla pracovat (její startovací symbol se vyskytuje v prostředí), ale všechny výskyty jejího startovacího symbolu zabraly jiné komponenty (se stejným startovacím symbolem), je derivace zablokována, odvozování končí. Příklad 6.3 - C = ({A, B, a}, {a}, K, A), kde 1Z = {(A, {BB}), (A, {a}), (B, {A})} Ukázky derivací s použitím b a t módu odvození: A =H BB =H AB =H aB =h aA =H aBB =h aBA =h .. . A =>t B2 =>t A2 =>t B4 =>t A4 =>t B8 =>t A8 =>t a8 S použitím módů odvození b at jsou generovány tyto jazyky: L(C,b) = {an | n > 0} £) = L4 = j a2™ n > 0 j (také u OL-systému v příkladu 5.1 na straně 67). Veta 6.2 Sekvenční kolonie jsou ve své generativní síle stejně silné jako bezkontextové jazyky: Jŕ{CF) ~ ££(COLh) (6.2) Důkaz: Podle bezkontextové gramatiky G = (N, T, P, S) vytvoříme kolonii s b módem odvození C = (V, T, 1Z, uj0) jednoduše takto: • odstraníme přímou rekurzi (pravidla, kde na pravé straně je neterminál z levé strany A —► aA(3, přepíšeme na dvojici pravidel A —► A', A' —► aAf3), symboly A' jsou nově přidané, • pravidla se stejnou levou stranou shrneme vždy do jedné komponenty (tj. budeme mít tolik komponent, kolik neterminálů), • V = N U T U {A' | A G N}, • uq = S, • U = {(A, {A'}) I A G N} U |(A', {« | (A a) G P}) A G iv}. Kapitola 6 Formální systémy 83 Odvození bude probíhat prakticky stejně jako v bezkontextové gramatice, až na mezikroky provedené pro odstranění rekurze. Opačný postup vyžaduje oddělení terminálů od symbolů, které lze přepisovat. Z kolonie C = (V, T, 1Z, uj0) vytvoříme bezkontextovou gramatiku G = (N, T, P, S) takto: • pro každý symbol terminálni abecedy a E T vytvoříme nový (nově přidaný) neterminál Na, • v gramatice budou pravidla Na —► a pro každý symbol a E T, • pravidla gramatiky vytvoříme z komponent tak, že v jazyce komponenty všechny terminály a nahradíme novými neterminály Na, označme o. řetězec, který vznikl z řetězce a tímto nahrazením, • N = V - T U {Na | a E T} U {S}, S<£V, • P = {Na -+ a | a E T} U [ň -+ h \ J2 \ ... | (A, {h, h,...}) E Ti] U {S -+ ~Q} □ Veta 6.3 Sekvenčnš-paralelní kolonie jsou silnější než bezkontextové jazyky: Jŕ{CF) C ££{COLt) (6.3) Důkaz: Podle bezkontextové gramatiky G = (N, T, P, S) vytvoříme kolonii s t módem odvození C = (V, T, 1Z, uúq) jednoduše takto: • stejně jako v předchozím důkazu odstraníme přímou rekurzi (pravidla, kde na pravé straně je neterminál z levé strany A —► aAfi, přepíšeme na dvojici pravidel A —► A', A' —► ctAf3), symboly A' jsou nově přidané, • pravidla se stejnou levou stranou shrneme vždy do jedné komponenty (tj. budeme mít tolik komponent, kolik neterminálů), • V = N U T U {A' | A E N}, • uq = S, • U = {(A, {A'}) I A E N} U {A} U {a | (A a) E P}) A E iv}. Kapitola 6 Formální systémy 84 Rozdíl oproti předchozímu důkazu je v definici množiny 1Z, kde musíme zajistit možnost simulace sekvenčního odvození. Zatímco při použití t módu odvození v kolonii se v jednom kroku odvození přepisují všechny symboly, zde musí být možnost přepsat jakoby jen jeden výskyt symbolu A a ostatní nechat bez přepsání (v simulaci na jeden výskyt symbolu A použijeme dotyčné pravidlo, na ostatní použijeme přepis na A přes A'). Vlastní podmnožinu lze dokázat například jazykem L4 = j a2" n > 0 j generovaným kolonií s t módem odvození v příkladu 6.3 na straně 82. Tento jazyk není bezkontextový, což se dá dokázat například pomocí Pumping lemma. □ Příklad 6.4 - C = ({M, N, P, a, b}, {a, b}, TI, MM), kde množina TZ obsahují (M,{PPNP,PNPP,s}), (P, {a}), (N, {M}), (P, {b}) Ukázky derivace komponenty MM MM MM MM (P, {b}) : s použitím wp a sp módu odvození: >wp PPNPM ^wp baMP ^wp baa >wp PPNPM ^wp aPMb ^wp aaPNPPb ->sp PPNPM =^sp PaMb odvození je zabloi , rrivrivi =?wp anvio =?wp aari\rro =?wp aaaMPbb =^wp aaabbb PPNPM =^sp PaMb odvození je zablokováno IVl ^sp PPNPM ^sp abMPPNPP ^sp abbaMPP ^sp abbaab S použitím módů odvození wp a sp jsou generovány tyto jazyky: v 2, wp) = L24 = |w G {a, b}* \w\a — \w\b < 1, \w\ = 3n, n > o| L(C, sp) = L25 = |w G {a, b}* \w\a = \w\b, \w\ = 6n, n > o| — {a%b\ blal G {a,b}* \w\a = Mb, Í > 1} V příkladu 6.4 vidíme u sp módu využití blokování odvození v případě, že v prostředí je právě jeden symbol P, přičemž máme dvě komponenty s tímto startovacím symbolem. Zde je blokování využito pro zajištění stejného počtu symbolů a a b v generovaném slově. Kolonie s wp a sp módem odvození jsou silnější než bezkontextové jazyky, důkaz by byl stejný jako u důkazu věty 6.2 na straně 82. Na příkladu 6.5 vidíme využití blokování odvození některých slov, zde použito k synchronizování generování obou stejných polovin slova. Kapitola 6 Formální systémy 85 Příklad 6.5 - C = ({P, A, B, a, b}, {a, b}, TZ, PP), v množině TZ jsou komponenty (P,{aA,bB,e}), (A, {P}), (B, {P}), (P,{aA,bB,e}), (A, {P}), (B, {P}) Ukázka derivace s použitím sp (silně paralelního) módu odvození: PP =^sp aAaA =^sp aPaP =^sp aaAaaA =^sp aaPaaP =^sp aabBaabB =>, =^sp aabPaabP =^sp aabaab Tato kolonie s sp módem odvození generuje jazyk L(C, wp) = Lb = {ww \ w e {a, b}*} S wp módem odvození bychom vygenerovali jazyk {a, b}*. Jistou možnost blokování některých odvození však lze použít i u wp módu odvození (nekonečným cyklem), jak vidíme na příkladu 6.6. Příklad 6.6 - C = ({P, Q, R, X, Y, B, B', a, b}, {a, b}, TZ, PP), v množině TZ jsou komponenty (P,{aQX,bRX,Y}), (Q, {P}), (R, {P}), (X, {s}), (Y, {s}), (B, {B'}), (P,{aRY,bQY,X}), (Q, {B}), (R, {B}), (X, {B}), (Y, {B}), (B', {B}) Ukázka derivací s použitím wp (slabě paralelního) módu odvození: PP =^wp aQXaRY =^wp aPaP =^wp abRXabQY =^wp abPabP =^wp abXabY =^wp =^wp abab PP =^wp aQXbQY =^wp aPbB =^wp aYbB' =^wp abB =^wp abB' =^wp ... S použitím módu odvození wp je generován jazyk L5. Kdybychom zde použili při odvozování sp mód, získali bychom prázdný jazyk. Seznam použitých jazyků Li = {anbn | n > 1} » příklad 1.1, Pumping lemma.......................... » příklad 1.6, Parikhův vektor.......................... » příklad 1.9, Parikhův vektor a reg. jazyky............. » příklad 1.11, Dyckův jazyk ........................... důkaz věty 5.6, i áf(T0L) ............................ L2 = {anbncn | n > 0} » příklad 1.2, ^ áf (CF), Pumping lemma............... příklad 1.13, Í^{CF), Dyckův jazyk ................ » důkaz věty 1.13, áf(CF), Průnik jazyků ............ » příklad 3.2, Zásobníkový automat se dvěma zásobníky » příklad 3.4, Turingův stroj ............................ příklad 5.7, G ^(ETOL), ETOL-systém................ » příklad 1.4, „žf (CF), Pumping lemma.............. » příklad 5.1, G „šf (OL), OL-systém..................... » příklad 6.3, G Jz?(COLt), kolonie s t módem odvození » » příklad 1.3, (CF), Pumping lemma příklad 1.19, bezkontextová substituce . 86 Seznam použitých jazyků 87 L5 = {ww | w G {a, b}*} příklad 1.5, £ J?(CF), Pumping lemma................................ 8 » příklad 4.1, G =žf (1), nezkracující gramagika ........................... 57 » příklad 6.5, G J£{COLsp), kolonie s sp módem odvození ............... 85 » příklad 6.6, G áf(COLwp), kolonie s wp módem odvození .............. 85 L6 = {anbman | 0 < m < n) » v poznámce ^ J£(CF), Pumping lemma............................... 9 L7 = {a3nbn+2aAcn | n > 1} » příklad 1.6, Parikhův vektor........................................... 9 » příklad 1.9, Parikhův vektor a reg. jazyky.............................. 11 L8 = {a^fo™-1 | n > 1} » příklad 1.6, Parikhův vektor........................................... 9 » příklad 1.12, Dyckův jazyk ............................................ 14 Lg = {ďWck | i,j, k > 1, i = j nebo j = fc} » příklad 1.7, Parikhův vektor........................................... 10 » příklad 1.14, sjednocení jazyků ........................................ 15 » příklad 1.16, uzavřenost vzhledem k zrcadlení......................... 17 » příklad 1.17, substituce................................................ 18 L10 = {a*bc} U {ďbanc \ n > 0,p je prvočíslo} příklad 1.8, i ^(CF), Parikhův vektor................................ 11 Ln = [an%n | n > l} » příklad 1.8, i ^(CF), Parikhův vektor................................ 11 L12 = |a"26" | 1 < n < 8} » Parikhův vektor....................................................... 11 Li3 = {ani6nia"26n2 ... anfe6nfe | fc > 0, n,t > 1, 1 < i < k} » příklad 1.18, G =5?(CF), uzávěrové vlastnosti........................... 19 Seznam použitých jazyků 88 L14 = [wcwR I w G {a,b}*} » příklad 2.1, G áf(ZA), zásobníkový automat........................... 24 » příklad 2.2, zásobníkový automat - stavový diagram .................. 25 » příklad 2.3, převod gramatiky na zásobníkový automat................ 29 L15 = {ancbnck | n > 0, fc > 0} » příklad 2.4, jednostavový zásobníkový automat........................ 31 » příklad 2.5, převod zásobníkového automatu na gramatiku............ 33 Lw = {wwR I w G {a, &}*} » příklad 2.6, G áf(CF), průnik s reg. jazykem........................... 36 » důkaz věty 2.9, ^ áf(DZA), deterministické bezkontextové jazyky..... 37 L17 = {anan | n > 0} = {a2n \ n > 0} příklad 2.6, G Jŕ(CF), průnik CF a i?LG.............................. 36 -^18 = G {a,6,c}* |w|a = |w|b = |w|cj příklad 2.7, £ Jr(CF), průnik CF a i?LG.............................. 37 L19 = L2 - {^} = {an6ncn | n > 1} » příklad 3.5, převod gramatiky na Turingův stroj ....................... 49 příklad 5.4, G Jŕ(E0L), EOL-systém.................................... 70 » příklad 6.2, G Jŕ(MAT), maticová gramatika .......................... 79 L20 = {a3'2" | n > 1} příklad 5.2, G -š?(0L), OL-systém....................................... 68 L2i = {a, aa] důkaz věty 5.1, £ (OL)............................................... 68 příklad 5.5, G Jŕ(EOL), EOL-systém.................................... 71 L22 = L4 U {e} = {a2" n > o} U {^} příklad 5.6, G Jšŕ(TOL), TOL-systém.................................... 72 důkaz věty 5.5, £ (OL)............................................... 73 Seznam použitých jazyků 89 L23 = {ařVďV \i,j> 1} » příklad 6.1, G Jŕ(MAT), maticová gramatika 78 L24 = |w G {a, 6}* < 1, M = 3n, n > 0 příklad 6.4, G áf(COLwp), kolonie s u>p módem odvození .............. 84 £25 = [w G {a, &}* |w| = 6n, n > 0> — {ďb\ Uď \ i>l} příklad 6.4, G Jŕ(COLsp), kolonie s sp módem odvození ............... 84