TEORIE JAZYKŮ A AUTOMATŮ II

SLEZSKA´ UNIVERZITA V OPAVEˇ FILOZOFICKO-PRˇI´RODOVEˇDECKA´ FAKULTA ´ STAV INFORMATIKY U

TEORIE JAZYKU˚ A AUTOMATU˚ II Studijnı´ opora Poslednı´ zmeˇny: 3. za´rˇ´ı 2007

Mgr. Sˇa´rka Vavrecˇkova´ [email protected] http://fpf.slu.cz/~vav10ui

Opava 2007

Obsah

´ vod U 1

2

1

Vlastnosti bezkontextovyćh jazyku˚ 1.1 Krite´ria bezkontextovosti . . . . . . . . . . . . . . . . . . . . . . . 1.1.1 Pumping lemma pro bezkontextove´ jazyky . . . . . . . . . 1.1.2 Parikhu˚v vektor . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.3 Dycku˚v jazyk . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Jak poznat zda je jazyk bezkontextovy´ . . . . . . . . . . . . . . . . 1.3 Uza´veˇrove´ vlastnosti bezkontextovyćh jazyku˚ . . . . . . . . . . . 1.3.1 Regula´rnı´ operace . . . . . . . . . . . . . . . . . . . . . . . 1.3.2 Operace, vzhledem k nimzˇ je jesˇteˇ trˇ´ıda L (CF ) uzavrˇena 1.3.3 Operace, vzhledem k nimzˇ trˇ´ıda L (CF ) nenı´ uzavrˇena . . 1.4 Uza´veˇrove´ vlastnosti jako krite´rium bezkontextovosti . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

Za´sobnı´kovy´ automat 2.1 Definice za´sobnı´kove´ho automatu . . . . . . . . . . . . . . . . . . . . 2.2 Vztah mezi ru˚zny´mi typy za´sobnı´kovyćh automatu˚ . . . . . . . . . . 2.3 Vztah za´sobnı´kovyćh automatu˚ a bezkontextovyćh jazyku˚ . . . . . . 2.4 Za´sobnı´kove´ automaty a uza´veˇrove´ vlastnosti bezkontextovyćh jazyku˚ 2.5 Deterministicke´ bezkontextove´ jazyky . . . . . . . . . . . . . . . . . . 2.5.1 Deterministicky´ za´sobnı´kovy´ automat . . . . . . . . . . . . . . 2.5.2 Uza´veˇrove´ vlastnosti deterministickyćh bezkontextovyćh jazyku˚ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

i

3 3 3 9 12 14 15 15 16 18 19 21 21 25 28 35 37 37 38

ii 3

4

5

6

Jazyky typu 0 3.1 Gramatiky typu 0 . . . . . . . . . . . . . . . . . . . 3.2 Stroje rozpozna´vajıćı´ jazyky typu 0 . . . . . . . . . 3.2.1 Za´sobnı´kovy´ automat se dveˇma za´sobnı´ky 3.2.2 Turingu˚v stroj . . . . . . . . . . . . . . . . . 3.2.3 Varianty Turingova stroje . . . . . . . . . . 3.3 Vztah Turingovyćh stroju˚ k jazyku˚m typu 0 . . . . Jazyky typu 1 4.1 Gramatiky typu 1 . . . . . . . . . . . . . . . . . . 4.2 Kurodova norma´lnı´ forma pro gramatiky typu 1 4.3 Linea´rneˇ ohranicˇeny´ automat . . . . . . . . . . . 4.4 Uza´veˇrove´ vlastnosti jazyku˚ typu 1 . . . . . . . . L-syste´my 5.1 Paralelnı´ odvozovańı´ . . . . . . . . . . 5.2 0L-syste´my . . . . . . . . . . . . . . . . 5.3 E0L-syste´my . . . . . . . . . . . . . . . 5.4 T0L-syste´my . . . . . . . . . . . . . . . 5.5 ET0L-syste´my . . . . . . . . . . . . . . 5.6 Mozˇnosti vyuzˇitı´ L-syste´mu˚ v grafice

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . .

. . . . . .

Forma´lnı´ syste´my 6.1 Derivace v gramatikaćh . . . . . . . . . . . . . . . 6.2 Gramatiky pouzˇ´ıvajıćı´ rˇ´ızenou sekvencˇnı´ derivaci 6.3 Gramaticke´ syste´my . . . . . . . . . . . . . . . . . 6.3.1 Kolonie . . . . . . . . . . . . . . . . . . . . .

Seznam pouzˇityćh jazyku˚

. . . . . .

. . . .

. . . . . .

. . . .

. . . . . .

. . . .

. . . . . .

. . . .

. . . . . .

. . . .

. . . . . .

. . . .

. . . . . .

. . . .

. . . . . .

. . . .

. . . . . .

. . . .

. . . . . .

. . . .

. . . . . .

. . . .

. . . . . .

. . . .

. . . . . .

. . . .

. . . . . .

. . . .

. . . . . .

. . . .

. . . . . .

. . . .

. . . . . .

. . . .

. . . . . .

. . . .

. . . . . .

. . . .

. . . . . .

. . . .

. . . . . .

40 40 42 42 44 48 49

. . . .

56 56 58 60 63

. . . . . .

65 65 66 69 72 74 75

. . . .

77 77 78 80 81 87

Seznam definic

Definice 1.1 Definice 1.2 Definice 1.3 Definice 1.4 Definice 1.5 Definice 2.1 Definice 2.2 Definice 2.3 Definice 2.4 Definice 2.5 Definice 2.6 Definice 3.1 Definice 3.2 Definice 3.3 Definice 3.4 Definice 3.5 Definice 3.6 Definice 3.7 Definice 3.8 Definice 3.9 Definice 4.1 Definice 4.2 Definice 4.3 Definice 4.4

Parikhu˚v vektor slova . . . . . . . . . . . . . . . Parikhu˚v vektor jazyka . . . . . . . . . . . . . . Linea´rnı´ podmnozˇina mnozˇiny Nn . . . . . . . . Semilinea´rnı´ mnozˇina . . . . . . . . . . . . . . . Dycku˚v jazyk . . . . . . . . . . . . . . . . . . . . Za´sobnı´kovy´ automat . . . . . . . . . . . . . . . Konfigurace za´sobnı´kove´ho automatu . . . . . . Prˇechod mezi konfiguracemi . . . . . . . . . . . Za´kladnı´ typy za´sobnı´kovyćh automatu˚ . . . . . Deterministicky´ ZA . . . . . . . . . . . . . . . . . Deterministicky´ bezkontextovy´ jazyk . . . . . . Gramatika typu 0 . . . . . . . . . . . . . . . . . . Kurodova norma´lnı´ forma pro gramatiky typu 0 Za´sobnı´kovy´ automat se dveˇma za´sobnı´ky . . . Konfigurace a prˇechod mezi konfiguracemi . . . Turingu˚v stroj . . . . . . . . . . . . . . . . . . . . Konfigurace Turingova stroje . . . . . . . . . . . Relace prˇechodu mezi konfiguracemi . . . . . . Rekurzı´vneˇ spocˇetny´ jazyk . . . . . . . . . . . . Rekurzı´vnı´ jazyk . . . . . . . . . . . . . . . . . . Nezkracujıćı´ gramatika . . . . . . . . . . . . . . Kontextova´ gramatika . . . . . . . . . . . . . . . Kurodova norma´lnı´ forma pro gramatiky typu 1 Linea´rneˇ ohranicˇeny´ automat . . . . . . . . . . . iii

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

9 9 10 10 12 22 22 22 23 37 37 40 40 43 43 44 45 46 49 49 56 56 58 60

iv Definice 4.5 Definice 5.1 Definice 5.2 Definice 5.3 Definice 5.4 Definice 5.5 Definice 5.6 Definice 5.7 Definice 5.8 Definice 5.9 Definice 6.1 Definice 6.2

Konfigurace linea´rneˇ ohranicˇene´ho automatu 0L-sche´ma . . . . . . . . . . . . . . . . . . . . . 0L-syste´m . . . . . . . . . . . . . . . . . . . . . Jazyk 0L-syste´mu . . . . . . . . . . . . . . . . . E0L-sche´ma . . . . . . . . . . . . . . . . . . . . E0L-syste´m . . . . . . . . . . . . . . . . . . . . Jazyk E0L-syste´mu . . . . . . . . . . . . . . . . T0L-sche´ma . . . . . . . . . . . . . . . . . . . . T0L-syste´m . . . . . . . . . . . . . . . . . . . . Jazyk T0L-syste´mu . . . . . . . . . . . . . . . . Maticova´ gramatika . . . . . . . . . . . . . . . Kolonie . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

60 66 67 67 70 70 70 72 72 72 78 82

´ vod U

Tento studijnı´ text je urcˇen pro studenty kurzu Teorie jazyku˚ a automatu˚ II a navazuje na obdobny´ studijnı´ text pro prˇedchozı´ kurz Teorie jazyku˚ a automatu˚ I. Prˇedpokla´dajı´ se znalosti v rozsahu prˇedchozı´ho kurzu, prˇedevsˇ´ım z oblasti bezkontextovyćh a regula´rnıćh gramatik. Samotny´ vy´klad sesta´va´ zejmeńa z definic, veˇt a du˚kazu˚, ovsˇem veˇtsˇinou nejde o du˚kazy v prave´m smyslu slova, jsou hodneˇ zjednodusˇene´. „Opravdovy´“ du˚kaz nenı´ jen popis konstrukce, ale musı´ by´t doka´zańo, zˇe tato konstrukce je spra´vna´. Text je hojneˇ doprova´zen prˇ´ıklady, ktere´ majı´ zvy´sˇit na´zornost vy´kladu. V textu jsou graficky vyznacˇeny neˇktere´ cˇa´sti: Prˇı´klad 0.1 Takto jsou vyznacˇeny prˇ´ıklady. Jsou cˇ´ıslovańy v za´vislosti na cˇ´ısle kapitoly a je na neˇ v textu odkazovańo pomocı´ tohoto cˇ´ıslovańı´.

Definice 0.1 (Definovany´ pojem) Takto je vyznacˇena definice jednoho nebo vıće pojmu˚. Definice jsou cˇ´ıslovańy v za´vislosti na cˇ´ısle kapitoly.

✍

Veˇta 0.1 Takto jsou vyznacˇeny veˇty, opeˇt jsou cˇ´ıslovańy. Kapitola 1 jesˇteˇ nebyla, proto zde ma´me jako cˇ´ıslo kapitoly 0.

✎

Lemma 0.2 Lemmata (pomocne´ veˇty) jsou vyznacˇena podobneˇ jako veˇty, cˇ´ıslovańı´ je simultańnı´ s veˇtami. Lemma obvykle obsahuje tvrzenı´, ktere´ je pak pouzˇito v du˚kazu „veˇtsˇ´ı“ veˇty.

1

✎

´ VOD U

2

Du˚kaz: Takto vyznacˇujeme du˚kaz veˇty nebo lemmatu. Kazˇda´ veˇta by meˇla by´t doka´zańa, zde vsˇak, stejneˇ jako v prˇedchozı´m studijnı´m textu pro kurz Teorie jazyku˚ a automatu˚ I, jsou pod pojmem du˚kaz obvykle mıńeˇny spı´sˇe konstrukce naznacˇujıćı´ du˚kaz nebo vztah. Du˚kazy koncˇ´ı symbolem pra´zdne´ho cˇtverecˇku. 2

"

Mysˇlenka du˚kazu: Mysˇlenka du˚kazu naznacˇuje, jak by mohl by´t vytvorˇen du˚kaz. Narozdı´l od du˚kazu samotne´ho nekoncˇ´ı symbolem cˇtverecˇku.

y

Du˚sledek 0.3 Takto je vyznacˇen du˚sledek prˇedchozıćh veˇt. Obvykle je take´ uvedeno, ze kteryćh veˇt tento du˚sledek vyply´va´, a nebo na´sleduje du˚kaz stejneˇ jako za kteroukoliv veˇtou.

➠

Pozna´mka: Takto je vyznacˇena pozna´mka, ve ktere´ je obvykle okomentovań du˚kaz, veˇta nebo definice.

❁

Kapitola

1

Vlastnosti bezkontextovyćh jazyku˚ Tato kapitola doplnˇuje znalosti zı´skane´ v kurzu Teorie jazyku˚ a automatu˚ I. Zameˇrˇ´ıme se zde na dosud neprobrane´ vlastnosti bezkontextovyćh jazyku˚, a to krite´ria bezkontextovosti (urcˇujıćı´, zda jazyk nenı´ bezkontextovy´) a uza´veˇrove´ vlastnosti.

1.1

Krite´ria bezkontextovosti

1.1.1 Pumping lemma pro bezkontextove´ jazyky Pumping lemma pro bezkontextove´ jazyky bude podobne´ obdobne´mu lemmatu pro regula´rnı´ jazyky probı´rane´mu v prˇedchozı´m kurzu. Jde o to zachytit „nekonecˇne´ smycˇky“, tentokra´t v potencia´lnı´ bezkontextove´ gramatice, a vyuzˇ´ıt toho v du˚kazu sporem (dokazujeme obvykle, zˇe kdyzˇ dany´ jazyk nema´ tuto vlastnost, pak nemu˚zˇe by´t bezkontextovy´). Veˇta 1.1 (Pumping lemma) Necht’L je bezkontextovy´ jazyk. Pak existujı´ prˇirozena´ cˇ´ısla p a q takova´, zˇe kazˇde´ slovo w ∈ L, |w| > p, mu˚zˇeme rozlozˇit na peˇt cˇa´stı´ w = x · y · z · u · v, prˇicˇemzˇ • |y · u| > 0 (v alesponˇ jedne´ z teˇchto dvou cˇa´stı´ musı´ by´t alesponˇ jeden symbol), • |yzu| ≤ q (prostrˇednı´ cˇa´st ma´ omezenou de´lku), • x · y i · z · ui · v ∈ L pro kazˇde´ i ≥ 0 (po iteraci teˇchto dvou cˇa´stı´ slovo zu˚sta´va´ v jazyce). Nejdrˇ´ıv si veˇtu rozebereme a potom teprve uvedeme du˚kaz. 3

✎

KAPITOLA 1 VLASTNOSTI BEZKONTEXTOVYĆH JAZYKU˚

4

S

S

A

A A

x

y

z

A

u

v

x

y (a) Odvozenı´ slova xyzuv

A

y

z

u

v

u

(b) Odvozenı´ slova xy 2 zu2 v

Obra´zek 1.1: Na´kres pouzˇitı´ Pumping lemma Mysˇlenka du˚kazu: Podı´va´me se na obra´zek 1.1. Veˇta se zakla´da´ na te´to u´vaze: 1. Kdyzˇ je jazyk bezkontextovy´, pak pro neˇj musı´ existovat bezkontextova´ gramatika. 2. V te´to gramatice musı´ pro kazˇde´ slovo jazyka existovat derivace. 3. Oznacˇme n = |N | pocˇet netermina ´ lu˚ gramatiky a d de´lku nejdels ˇ´ıho pravidla gramatiky, d = max |α| (A → α) ∈ P ) pro neˇjake´ A ∈ N . Pak v kazˇde´m kroku derivace se slovo prodlouzˇ´ı nejvy´sˇe o d znaku˚, a tedy po n krocıćh odvozenı´ n · d se prodlouzˇ´ı maxima´lneˇ o n · d znaku˚. 4. Derivace slov delsˇ´ıch nezˇ n · d znaku˚ musı´ by´t proto delsˇ´ı nezˇ n. 5. Kdyzˇ je derivace delsˇ´ı nezˇ n, tak to znamena´, zˇe alesponˇ jeden netermina´l musel by´t v pru˚beˇhu derivace prˇepisovań vıće nezˇ jednou (podle obra´zku 1.1a je to netermina´l A). 6. Kdyzˇ rozdeˇlı´me dostatecˇneˇ dlouhe´ slovo w ∈ L podle obra´zku 1.1a na peˇt cˇa´stı´ w = x·y·z·u·v, tak vlastneˇ zkouma´me, zda v prˇ´ıpadne´ derivaci existuje neˇktery´ opakovaneˇ prˇepisovany´ netermina´l. Pokud jde o bezkontextovy´ jazyk, tak takovy´ netermina´l (cyklus) musı´ existovat, ale nenı´ rˇecˇeno, zˇe ho objevı´me „na´hodneˇ“, okamzˇiteˇ a napoprve´. 7. Kdyzˇ se na´m takovy´ cyklus podarˇ´ı najı´t, pak (podle obra´zku 1.1b) mu˚zˇeme 1 1 v te´to derivaci „pumpovat“ – prˇi prˇepsańı´ druhe´ho zobrazene´ho vy´skytu symbolu A prosteˇ pouzˇijeme to pravidlo, ktere´ jsme pu˚vodneˇ pouzˇili prˇi

y


5

prˇepsańı´ prvnı´ho zobrazene´ho vy´skytu symbolu A a tak pokracˇujeme v cele´m podstromeˇ. Krajnı´ rˇeteˇzce x a v a nejvnitrˇneˇjsˇ´ı rˇeteˇzec z zu˚stanou takove´, jake´ byly, jen rˇeteˇzce y a u se zdvojı´. Cestu mezi dveˇma vy´skyty symbolu A jsme vlastneˇ zdvojili, ale mu˚zˇeme ji opakovat kolikra´t chceme, a nebo dokonce oba vy´skyty symbolu A ztotozˇnit (pro prvnı´ vy´skyt symbolu A pouzˇijeme to pravidlo, ktere´ jsme v pu˚vodnı´ derivaci pouzˇili pro druhy´), to odpovı´da´ hodnoteˇ i = 0 ve veˇteˇ 1.1. Jesˇteˇ zby´va´ cˇ´ıslo q. Jeho u´kolem je zajistit, aby de´lka cˇa´sti derivace mezi dveˇma vy´skyty A nebyla nekonecˇna´. Toto cˇ´ıslo mu˚zˇe by´t stanoveno zcela na´hodneˇ (samozrˇejmeˇ nikoliv nekonecˇno), naprˇ´ıklad si mu˚zˇeme stanovit, zˇe na obra´zku 1.1b v podstromeˇ s korˇenem ohodnoceny´m prvnı´m vy´skytem A je pouze to jedine´ dalsˇ´ı A, trˇetı´ se tam uzˇ nevyskytuje (ale v derivaci mezi S a prvnı´m A klidneˇ jesˇteˇ neˇjake´ by´t mu˚zˇe). Du˚kaz: Necht’ L je bezkontextovy´ jazyk. Pak existuje neˇktera´ bezkontextova´ gramatika G = (N, T, P, S) takova´, zˇe L = L(G). Pro zjednodusˇenı´ du˚kazu prˇedpokla´dejme, zˇe tato gramatika je v Chomske´ho norma´lnı´ formeˇ (tj. na prave´ straneˇ pravidla jsou bud’ dva netermina´ly nebo jeden termina´l). Derivacˇnı´ strom gramatiky v CNF je bina´rnı´ (kromeˇ prˇ´ımyćh cest k listu˚m). Oznacˇme n = |N |. Vezmeme si nynı´ neˇktere´ slovo w ∈ L takove´, zˇe v jeho derivaci je nejmeńeˇ dvakra´t prˇepisovań tenty´zˇ netermina´l (nazveˇme ho trˇeba A), to znamena´, zˇe v derivacˇnı´m stromeˇ tohoto slova se na cesteˇ od korˇene k neˇktere´mu listu nacha´zı´ dva uzly oznacˇene´ symbolem A, tyto uzly nazveme u1 a u2 (u1 je blı´zˇ korˇeni stromu). Pokud je na te´to cesteˇ vıće uzlu˚ oznacˇenyćh symbolem A nezˇ dva, zvolı´me uzel u1 tak, aby na cesteˇ od u1 k jake´mukoliv listu v jeho podstromeˇ byl jen jediny´ dalsˇ´ı uzel oznacˇeny´ symbolem A, tj. u2 . Prˇi splneˇnı´ podmıńky z prˇedchozı´ho odstavce je cesta od u1 ke ktere´mukoliv listu jeho podstromu dlouha´ nejvy´sˇe n + 1 uzlu˚. Protozˇe jde o bina´rnı´ strom, ma´ podstrom uzlu u1 nejvy´sˇe 2n listu˚. Touto hodnotou je tedy omezena de´lka slova y · z · u, proto lze zvolit q = 2n . Hodnota cˇ´ısla p uda´va´, jak dlouhe´ musı´ by´t slovo, aby v jeho derivacˇnı´m stromeˇ existovala cesta od korˇene k neˇktere´mu listu takova´, zˇe neˇktere´ dva uzly na te´to cesteˇ jsou ohodnoceny stejny´m netermina´lem. Z prˇedchozıćh odstavcu˚ du˚kazu je

"


6

zrˇejme´, zˇe vsˇechna slova nevyhovujıćı´ te´to podmıńce majı´ derivacˇnı´ strom, v neˇmzˇ jsou vsˇechny veˇtve kratsˇ´ı nezˇ n (tj. dlouhe´ nejvy´sˇe n − 1). Takovy´ derivacˇnı´ strom ma´ tedy nejvy´sˇe 2n−1 listu˚ (a tedy vygenerovanyćh termina´lu˚). Proto polozˇ´ıme p = 2n−1 . 2 Prˇı´klad 1.1 V tomto prˇ´ıkladu si uka´zˇeme, zˇe bezkontextovy´ jazyk splnˇuje Pumping lemma. L1 = {an bn | n ≥ 1} Protozˇe prˇedem nezna´me prˇesne´ hodnoty p a q z veˇty 1.1, budeme pouzˇ´ıvat symbolicky prˇ´ımo index p s prˇedpokladem, zˇe jde o „dostatecˇneˇ velke´“ cˇ´ıslo.

w = ap b p Zvolı´me toto rozdeˇlenı´:

x ap−1

y z a ε

u v b bp−1

Pak dosta´va´me slova ap−1 ai bi bp−1 = ap+i−1 bp+i−1 , cozˇ jsou pro jake´koliv cˇ´ıslo i ≥ 0 slova patrˇ´ıcı´ do jazyka L1 . Cˇ´ıslo p zde lze polozˇit naprˇ´ıklad p = 2 (nebo vysˇsˇ´ı). Tento jazyk generuje naprˇ´ıklad gramatika s teˇmito pravidly S → aSb | ab Pozna´mka: Pumping lemma je pouze implikace (ve tvaru „jestlizˇe je jazyk bezkontextovy´, pak splnˇuje tuto vlastnost“). Proto ji nelze pouzˇ´ıt tak, zˇe po zjisˇteˇnı´, zˇe jazyk splnˇuje danou vlastnost, bychom tento jazyk prohla´sili za bezkontextovy´. Naprˇ´ıklad jazyk {an bn | n ≥ 0} · {an bn cn | n ≥ 0} nenı´ bezkontextovy´, trˇebazˇe splnˇuje podmıńky Pumping lemma. Obecneˇ to lze rˇ´ıci o vsˇech jazycıćh, ktere´ sice nejsou bezkontextove´, ale lze je napsat jako zrˇeteˇzenı´ dvou jazyku˚, z nichzˇ alesponˇ jeden je bezkontextovy´. Pozna´mka: Pumping lemma se obvykle pouzˇ´ıva´ pro du˚kaz, zˇe neˇktery´ jazyk nenı´ bezkontextovy´, tedy du˚kaz sporem. Veˇtu obra´tı´me: A⇒B

⇐⇒

¬B ⇒ ¬A

V prˇepisu: Jestlizˇe jazyk je bezkontextovy´, pak ma´ danou vlastnost. je tote´zˇ jako Jestlizˇe jazyk nema´ danou vlastnost, pak nenı´ bezkontextovy´.

(1.1)

❁

❁


7

Prˇı´klad 1.2 Doka´zˇeme, zˇe jazyk L2 = {an bn cn | n ≥ 0} nenı´ bezkontextovy´. Zvolı´me slovo w = ap bp cp pro neˇktere´ dostatecˇneˇ velke´ cˇ´ıslo p. Mozˇna´ rozdeˇlenı´ tohoto slova jsou v tabulce. Musı´me bra´t v u´vahu konecˇnost konstanty q, v cˇa´sti yzu se proto nesmı´ vyskytovat „potencia´lneˇ nekonecˇny´“ index p. x

y

z

u

v

xy i zui v

ap bp cp−1 ap bp−1 ap bp−1 ap bp−2 ...

c b b bb

ε c ε ε

ε ε c cc

ε

ap bp cp−1+i ap bp−1+i cp ap bp−1+i cp−1+i ap bp−2+2i cp−2+2i

p−1

c cp−1 cp−2

pro i = 0 ap bp cp−1 ap bp−1 cp ap bp−1 cp−1 ap bp−2 cp−2

∈ / L2 ∈ / L2 ∈ / L2 ∈ / L2

Prˇi splneˇnı´ podmıńek Pumping lemma (|yu| > 0, |yzu| ≤ q) vidı´me na tabulce, zˇe „pumpujıćı´“ cˇa´st yu mu˚zˇe zachytit nejvy´sˇe dva druhy symbolu˚ (bud’ jen symboly a, nebo jen b, c, a nebo jen a, b, b, c), tedy prˇiby´vat (nebo uby´vat pro i = 0 nemohou za´rovenˇ symboly a, b i c a proto prˇi jake´mkoliv mozˇne´m rozdeˇlenı´ vznikajı´ iteracı´ slova nepatrˇ´ıcı´ do jazyka L2 . Proto L2 ∈ / L (CF )1 .

Prˇı´klad 1.3 o n 2 Doka´zˇeme, zˇe jazyk L3 = an n ≥ 0 nenı´ bezkontextovy´. p2

Opeˇt zvolı´me neˇjake´ slovo w = a ∈ L3 s „dostatecˇneˇ velky´m“ indexem p. Toto 2 slovo rozdeˇlı´me na´sledovneˇ: ap = ax1 ax2 ax3 ax4 ax5 a musı´ platit x2 + x4 > 0, x2 + x3 + x4 ≤ q Prˇed iteracı´: p 2 = x1 + x2 + x3 + x4 + x5 Po iteraci: m2 = x1 + i · x2 + x3 + i · x4 + x5 = i · (x2 + x4 ) + (x1 + x3 + x5 ) Zı´skali jsme rovnici, v jejichzˇ obou cˇa´stech oddeˇlenyćh rovnı´tkem jsou funkce. Zatı´mco leva´ cˇa´st rovnice roste exponencia´lneˇ, prava´ linea´rneˇ (je to linea´rnı´ funkce) a tedy mnohem pomaleji. At’stanovı´me indexy x2 a x4 jakkoliv, vzˇdy se najde cˇ´ıslo i, pro ktere´ soucˇet indexu˚ nenı´ roven druhe´ mocnineˇ zˇa´dne´ho cˇ´ısla. L3 ∈ / L (CF ).

1

CF znacˇ´ı bezkontextove´ gramatiky, L (CF ) znamena´ trˇ´ıdu (tj. mnozˇinu) jazyku˚ generovanyćh bezkontextovy´mi gramatikami, tj. bezkontextove´ jazyky.


8

Prˇı´klad 1.4 n o n Pomocı´ Pumping lemma doka´zˇeme, zˇe jazyk L4 = a2 n ≥ 0 nenı´ bezkontextovy´. Du˚kaz bude podobny´ prˇedchozı´mu. r Zvolı´me neˇjake´ slovo w = a2 ∈ L4 s „dostatecˇneˇ velky´m“ indexem r. Toto slovo r rozdeˇlı´me na a2 = ax1 ax2 ax3 ax4 ax5 a musı´ platit x2 + x4 > 0, x2 + x3 + x4 ≤ q Prˇed iteracı´: 2r = x1 + x2 + x3 + x4 + x5 Po iteraci: 2m = x1 + i · x2 + x3 + i · x4 + x5 = i · (x2 + x4 ) + (x1 + x3 + x5 )

Zı´skali jsme rovnici, v jejichzˇ obou cˇa´stech oddeˇlenyćh rovnı´tkem jsou funkce. Zatı´mco leva´ cˇa´st rovnice roste exponencia´lneˇ, prava´ linea´rneˇ (je to linea´rnı´ funkce) a tedy mnohem pomaleji. At’stanovı´me indexy x2 a x4 jakkoliv, vzˇdy se najde cˇ´ıslo i, pro ktere´ soucˇet indexu˚ nenı´ roven zˇa´dne´ mocnineˇ cˇ´ısla 2. Proto L4 ∈ / L (CF ).

Prˇı´klad 1.5 Doka´zˇeme, zˇe jazyk L5 = {ww | w ∈ {a, b}∗ } nenı´ bezkontextovy´. Tento jazyk se skla´da´ ze slov, ktera´ majı´ obeˇ poloviny stejne´. Pro du˚kaz si vybereme slovo w = ap bp ap bp , p > 4, q = 4 a doka´zˇeme, zˇe pro toto slovo neexistuje zˇa´dne´ rozdeˇlenı´, ktere´ by umozˇnˇovalo „pumpovańı´“ dle Pumping lemma. x

y

z

u

v

xy i zui v

ap bp−1 ap bp−1 ap bp−1 ...

b ε ε

ε b ε

a a ba

ap−1 bp ap−1 bp ap−1 bp

ap bp−1+i ap−1+i bp ap bp ap−1+i bp ap bp−1 (ba)i ap−1 bp

pro i = 0 ap bp−1 ap−1 bp ap bp ap−1 bp ap bp−1 ap−1 bp

∈ / L5 ∈ / L5 ∈ / L5

Jak vidı´me, veˇtsˇinou na´m u´plneˇ stacˇ´ı pro kazˇde´ rozdeˇlenı´ otestovat slovo pro i = 0. Mu˚zˇeme pokracˇovat dalsˇ´ımi rˇa´dky tabulky, ale vzˇdy dojdeme ke stejne´mu za´veˇru. Je to proto, zˇe kdyzˇ je cˇa´st yzu omezena konstantou, mu˚zˇe zabrat nejvy´sˇe dveˇ ru˚zne´ cˇa´sti ze cˇtyrˇ cˇa´stı´ vybrane´ho slova w (a prˇitom do yu musı´ padnout alesponˇ jeden symbol slova), tedy po iteraci pro zˇa´dne´ i kromeˇ i = 1 nedostaneme slovo, jehozˇ obeˇ poloviny jsou stejne´. Proto L5 ∈ / L (CF ).


9

Pozna´mka: Podobneˇ by mohl vypadat du˚kaz, zˇe jazyk L6 = {an bm an | 0 ≤ m ≤ n} nenı´ bezkontextovy´ (kdyby v definici tohoto jazyka nebyly nerovnosti, sˇlo by o bezkontextovy´ jazyk). Tento du˚kaz ponecha´va´me na cˇtena´rˇi.

❁

1.1.2 Parikhu˚v vektor Definice 1.1 (Parikhu˚v vektor slova) Necht’ L je neˇktery´ jazyk nad abecedou Σ, kde Σ = {a1 , a2 , . . . , an }, |Σ| = n. Parikhu˚v vektor slova w ∈ L je

✍

ψ(w) = (#a1 (w), #a2 (w), . . . , #an (w)) kde #ai (w) znacˇ´ı pocˇet symbolu˚ ai ve sloveˇ w. Definice 1.2 (Parikhu˚v vektor jazyka) Necht’ L je neˇktery´ jazyk nad abecedou Σ, kde Σ = {a1 , a2 , . . . , an }, |Σ| = n. Parikhu˚v vektor jazyka L je mnozˇina Parikhovyćh vektoru˚ vsˇech slov tohoto jazyka, tedy

✍

ψ(L) = {ψ(w) | w ∈ L} Prˇı´klad 1.6 Vyzkousˇ´ıme si vytvorˇenı´ Parikhovyćh vektoru˚ pro slova i jazyky. L1 = {an bn | n ≥ 1} ψ(aaabbb) = (3, 3) ψ(L1 ) = {i · (1, 1) | i ≥ 1} L7 = {a3n bn+2 a4 cn | n ≥ 1} ψ(a6 b4 a4 c2 ) = (10, 4, 2) ψ(L7 ) = {(3n + 4, n + 2, n) | n ≥ 1} = = {n · (3, 1, 1) + (4, 2, 0) | n ≥ 1} L8 = {a2n bn−1 | n ≥ 1} zde je proble´m konstanta (−1) v exponentu – polozˇme k = n − 1, tedy k + 1 = n: ψ(L8 ) = {(2 · (k + 1), k) | k ≥ 0} = {k · (2, 1) + (2, 0) | k ≥ 0}


10

Z algebry si urcˇiteˇ pamatujeme operace s vektory – scˇ´ıtańı´ vektoru˚ a na´sobenı´ vektoru cely´m cˇ´ıslem: (x1 , x2 , . . . , xn ) + (y1 , y2 , . . . , yn ) = (x1 + y1 , x2 + y2 , . . . , xn + yn ) k · (x1 , , x2 , . . . , xn ) = (k · x1 , k · x2 , . . . , k · xn )

(1.2) (1.3)

Da´le budeme pouzˇ´ıvat toto znacˇenı´: N je mnozˇina prˇirozenyćh cˇ´ısel (zde vcˇetneˇ 0) Nn je mnozˇina vsˇech n-prvkovyćh vektoru˚ nad mnozˇinou N

✍

Definice 1.3 (Linea´rnı´ podmnozˇina mnozˇiny Nn) Linea´rnı´ podmnozˇina mnozˇiny Nn pro neˇjake´ n ∈ N je

✍

{¯ v0 + n1 · v¯1 + n2 · v¯2 + . . . + nk · v¯k | ni ∈ N, 1 ≤ i ≤ k, v¯j ∈ Nn , 0 ≤ j ≤ k} (ni jsou cˇ´ısla, v¯j jsou vektory cˇ´ısel) Definice 1.4 (Semilinea´rnı´ mnozˇina) Semilinea´rnı´ mnozˇina je konecˇne´ sjednocenı´ linea´rnıćh podmnozˇin mnozˇiny Nn .

✍

Veˇta 1.2 Pro kazˇdy´ bezkontextovy´ jazyk L je ψ(L) semilinea´rnı´ mnozˇina.

✎

Du˚kaz te´to veˇty by byl slozˇity´, proto ho zde nebudeme uva´deˇt. Prˇı´klad 1.7 L9 = {ai bj ck | i, j, k ≥ 1, i = j nebo j = k}

ψ1 (L9 ) = {i · (1, 1, 0) + k · (0, 0, 1) | i, k ≥ 1} ψ2 (L9 ) = {i · (1, 0, 0) + j · (0, 1, 1) | i, j ≥ 1} ψ(L9 ) = ψ1 (L9 ) ∪ ψ2 (L9 ) Parikhu˚v vektor jazyka L9 je jednocenı´ „dı´lcˇ´ıch“ linea´rnıćh mnozˇin, a tedy semilinea´rnı´ mnozˇina.

Pozna´mka: Stejneˇ jako Pumping lemma, i zde se jedna´ pouze o implikaci. Opeˇt budeme tuto veˇtu pouzˇ´ıvat v du˚kazu sporem – jestlizˇe Parikhu˚v vektor dane´ho jazyka nenı´ semilinea´rnı´ mnozˇina, pak to nenı´ bezkontextovy´ jazyk.

❁


11

Prˇı´klad 1.8 L10 = {a∗ bc} ∪ {ap ban c | n ≥ 0, p je prvocˇ´ıslo}

ψ1 (L10 ) = {i · (1, 0, 0) + (0, 1, 1) | i ≥ 0} ψ2 (L10 ) = {n · (1, 0, 0) + p · (1, 0, 0) + (0, 1, 1) | n ≥ 0, p je prvocˇ´ıslo} ψ(L10 ) = ψ1 (L10 ) ∪ ψ2 (L10 ) Mnozˇina ψ2 (L10 ) nenı´ linea´rnı´, a proto mnozˇina ψ(L10 ) nenı´ semilinea´rnı´. Neexistuje konecˇne´ sjednocenı´ linea´rnıćh mnozˇin popisujıćıćh mnozˇinu odvozenou z prvocˇ´ısel, to bychom museli postupneˇ vyjmenovat vsˇechna prvocˇ´ısla (a to by nebylo konecˇne´ sjednocenı´). Proto L10 ∈ / L (CF ). n o 2 L11 = an bn | n ≥ 1

ψ(L11 ) = {n2 ·(1, 0)+n·(0, 1) | n ≥ 1} nenı´ semilinea´rnı´ mnozˇina (je zde kvadraticka´ funkce). Proto L11 ∈ / L (CF ).

n o 2 Ale pozor! L12 = an bn | 1 ≤ n ≤ 8 ovsˇem je bezkontextovy´ jazyk, protozˇe je konecˇny´ (L12 ∈ L (F IN )) – Parikhu˚v vektor tohoto jazyka by mohl by´t slozˇen z Parikhovyćh vektoru˚ jednotlivyćh (osmi) slov jazyka, cozˇ je sjednocenı´ konecˇneˇ mnoha jednoprvkovyćh linea´rnıćh mnozˇin. Veˇta 1.3 Ke kazˇde´mu bezkontextove´mu jazyku L existuje regula´rnı´ jazyk R takovy´, zˇe ψ(L) = ψ(R).

✎

Prˇı´klad 1.9 L1 = {an bn | n ≥ 1} ψ(L1 ) = {n · (1, 1) | n ≥ 1}

R1 = ab(ab)∗ ,

ψ(R1 ) = ψ(L1 )

L7 = {a3n bn+2 a4 cn | n ≥ 1} ψ(a6 b4 a4 c2 ) = (10, 4, 2) ψ(L7 ) = {(3n + 4, n + 2, n) | n ≥ 1} = {n · (3, 1, 1) + (4, 2, 0) | n ≥ 1} R7 = (aaabc)∗ aaabcaaaabb, ψ(R7 ) = ψ(L7 )

Du˚kaz: Oznacˇme abecedu, nad kterou je definovań jazyk, Σ = {a1 , . . . , ar }, tj. ma´ celkem r prvku˚. Veˇta vyply´va´ z veˇty 1.2 na straneˇ 10 – kdyzˇ je Parikhu˚v vektor jazyka semilinea´rnı´ mnozˇina a tedy sjednocenı´ linea´rnıćh mnozˇin, tak postupneˇ

"


12

vsˇechny linea´rnı´ mnozˇiny ve tvaru {¯ v0 + n1 · v¯1 + n2 · v¯2 + . . . + nk · v¯k | ni ∈ N, 1 ≤ i ≤ k, v¯j ∈ Nn , 0 ≤ j ≤ k} rozlozˇ´ıme na jednotlive´ vekory na´sobene´ cˇ´ıslem ni · v¯i = ni (vi,1 , vi,2 , . . . , vi,r ), kde ni by´va´ bud’ konstanta nebo promeˇnna´ pro danou mnozˇinu naby´vajıćı´ hodnot ni ≥ Ki , 1 ≤ ni ≤ k. Regula´rnı´ jazyk pro ni · v¯i vytvorˇ´ıme takto: v ·K v ·K v ·K v v v ∗ a1i,1 i a2i,2 i . . . ari,r i · a1i,1 a2i,2 . . . ari,r

Tyto regula´rnı´ jazyky vektoru˚ linea´rnı´ mnozˇiny spojı´me opera´torem +. Vzniknou dı´lcˇ´ı regula´rnı´ jazyky pro jednotlive´ linea´rnı´ mnozˇiny. Ty takte´zˇ spojı´me opera´torem + (pro prˇipomenutı´ – tento opera´tor odpovı´da´ sjednocenı´). 2

Du˚sledek 1.4 Nad jednoprvkovou mnozˇinou bezkontextovost neprˇida´ na generativnı´ sı´le, tj. kazˇdy´ bezkontextovy´ jazyk nad jednoprvkovou abecedou je za´rovenˇ regula´rnı´. Kdyzˇ takovy´ jazyk nenı´ regula´rnı´, tak nenı´ ani bezkontextovy´ (je kontextovy´ nebo typu 0). Du˚kaz: Du˚kaz je trivia´lnı´ – v du˚kazu veˇty 1.3 jsme vlastneˇ „prˇemı´st’ovali“ jednotlive´ symboly v definici jazyka. Kdyzˇ vsˇak tı´mto zpu˚sobem proha´zı´me symboly v definici jazyka nad jednoprvkovou abecedou, generovany´ jazyk se nezmeˇnı´ (naprˇ´ıklad a1+2n pro n ≥ 0 je tote´zˇ jako a(aa)∗ ). Zrˇejmeˇji je mozˇne´ si tento postup uka´zat na pravidlech – kdyzˇ ma´me bezkontextove´ pravidlo A → ai Baj pro A, B ∈ N, T = {a}, indexy i, j ≥ 0, pak ekvivalentnı´ regula´rnı´ pravidlo vytvorˇ´ıme prˇesunem: A → ai aj B, prˇ´ıpadneˇ rˇeteˇzec symbolu˚ a rozdeˇlı´me s pouzˇitı´m pomocnyćh netermina´lu˚. Proto pro kazˇdou bezkontextovou gramatiku nad jednoprvkovou abecedou existuje regula´rnı´, ktera´ je s nı´ ekvivalentnı´. 2

➠

"

1.1.3 Dycku˚v jazyk Dyckovy jazyky se take´ nazy´vajı´ dobrˇe uza´vorkovane´ jazyky. Jde vlastneˇ o jazyky nad abecedou usporˇa´danyćh dvojic znaku˚ odpovı´dajıćıćh levy´m a pravy´m za´vorka´m ru˚znyćh typu˚.

✍


13

Definice 1.5 (Dycku˚v jazyk) Necht’ Σn = {a1 , a01 , a2 , a02 , . . . , an , a0n }, |Σn | = 2n je abeceda, n ≥ 1. Dycku˚v jazyk nad touto abecedou je jazyk generovany´ gramatikou s pravidly S → a1 Sa01 | a2 Sa02 | . . . | an Sa0n | SS | ε Prˇı´klad n 1.10 o Σ2 = (, ), [, ] (n = 2, |Σ2 | = 4) S → (S) [S] SS ε

S ⇒ SS ⇒ (S)S ⇒ ( [S] )S ⇒ ( [ ] )S ⇒ ( [ ] )[S] ⇒ ( [ ] ) [ ]

Lemma 1.5 (Vlastnosti Dyckova jazyka) Necht’Dn je Dycku˚v jazyk nad abecedou Σn . Pak pro jaka´koliv dveˇ slova u, v ∈ Σ∗n platı´

✎

1. Jestlizˇe u, v ∈ Dn , pak u · v ∈ Dn . 2. Jestlizˇe u ∈ Dn , pak ai · u · a0i ∈ Dn , 1 ≤ i ≤ n. 3. Kazˇde´ slovo w ∈ Dn , w 6= ε je ve tvaru ai · u · a0i v pro neˇjake´ 1 ≤ i ≤ n, u, v ∈ Dn . 4. Jestlizˇe ai · a0i · u ∈ Dn , pak u ∈ Dn . Du˚kaz: Du˚kazy jednotlivyćh tvrzenı´ z lemmatu ponecha´va´me na cˇtena´rˇi, jsou trivia´lnı´ a vyply´vajı´ prˇ´ımo z definice Dyckova jazyka. 2

"

Veˇta 1.6 Jestlizˇe L je bezkontextovy´ jazyk, pak existuje regula´rnı´ jazyk R a homomorfismus ϕ takove´, zˇe L = ϕ(D ∩ R) pro neˇjaky´ Dycku˚v jazyk D.

✎

Du˚kaz te´to veˇty zde nebudeme uva´deˇt. Prˇı´klad 1.11 L1 = {an bn | n ≥ 1} Vybereme vhodny´ regula´rnı´ jazyk R, homomorfismus ϕ a Dycku˚v jazyk D: R = aa∗ bb∗ (doda´ za´kladnı´ tvar slov – nejdrˇ´ıv a a potom b) ϕ je identita, D = ({S}, {a, b}, P, S), kde P = {S → aSb | SS | ε}


14

Pak je zrˇejme´, zˇe L1 = R ∩ D. Jiny´ mozˇny´ vy´beˇr: R = [∗ ]∗ o n D = ({S}, {[, ]}, P, S), kde P = S → [ S ] SS ε ϕ([ ) = a, ϕ( ] ) = b Prˇı´klad 1.12 L8 = {a2n bn−1 | n ≥ 1} ∗ ∗

R = 230 1 , jazyk D ma´ pravidla P = {S → 0S1 | 2S3 | SS | ε} ϕ(0) = aa, ϕ(1) = b, ϕ(2) = a, ϕ(3) = ε

Prˇı´klad 1.13 Doka´zˇeme, zˇe jazyk L2 = {an bn cn | n ≥ 0} nenı´ bezkontextovy´. V prˇedchozıćh prˇ´ıkladech jsme mohli pozorovat, zˇe regula´rnı´ jazyk zajisˇt’uje spra´vnou posloupnost symbolu˚ a Dycku˚v jazyk synchronizuje pocˇet symbolu˚ v jednotlivyćh podskupinaćh. Spra´vnou posloupnost symbolu˚ by mohl zajistit regula´rnı´ jazyk R = a∗ b∗ c∗ , ale nedoka´zˇeme najı´t Dycku˚v jazyk tak, aby doka´zal synchronizovat tenty´zˇ pocˇet symbolu˚ na vıće nezˇ dvou mı´stech. Proto L2 ∈ / L (CF ).

1.2

Jak poznat zda je jazyk bezkontextovy´

Nejlepsˇ´ım zpu˚sobem, jak urcˇit, zˇe je jazyk bezkontextovy´, a take´ prakticky jediny´m prˇ´ımy´m du˚kazem, je sestrojenı´ bezkontextove´ gramatiky generujıćı´ tento jazyk. V prˇedchozıćh sekcıćh jsme si uka´zali trˇi metody, ktere´ lze vyuzˇ´ıt prˇi du˚kazu sporem – Pumping lemma, Parikhu˚v vektor jazyka a Dycku˚v jazyk. Ve vsˇech trˇech prˇ´ıpadech jde o implikace, proto nejsou pouzˇitelne´ pro prˇ´ımy´ du˚kaz. Existuje vsˇak dalsˇ´ı mozˇnost – vyuzˇitı´ uza´veˇrovyćh vlastnostı´ bezkontextovyćh jazyku˚. Bezkontextove´ jazyky jsou naprˇ´ıklad uzavrˇeny vzhledem k operaci sjednocenı´, a tedy pokud lze neˇktery´ jazyk napsat jako sjednocenı´ dvou bezkontextovyćh


15

jazyku˚, pak jde o bezkontextovy´ jazyk. Uza´veˇrovy´m vlastnostem bezkontextovyćh jazyku˚ se budeme veˇnovat v sekci 1.3.

1.3

Uza´veˇrove´ vlastnosti bezkontextovyćh jazyku˚

Ve veˇtaćh a du˚kazech te´to sekce budeme pouzˇ´ıvat na´sledujıćı´ znacˇenı´ (nesouvisejıćı´ s pru˚beˇzˇny´m cˇ´ıslovańı´m jazyku˚ v tomto dokumentu): L1 = L(G1 ), G1 = (N1 , T1 , P1 , S1 ) L2 = L(G2 ), G2 = (N2 , T2 , P2 , S2 ), N1 ∪ N2 = ∅ vytva´rˇ´ıme L = L(G), G = (N, T, P, S) Narozdı´l od regula´rnıćh jazyku˚, zde budou du˚kazy postaveny na konstrukci gramatik, ne automatu˚.

1.3.1 Regula´rnı´ operace Veˇta 1.7 Trˇ´ıda bezkontextovyćh jazyku˚ je uzavrˇena vzhledem k operaci sjednocenı´. Du˚kaz: Vytvorˇ´ıme gramatiku G takovou, zˇe L(G) = L1 ∪ L2 : G = (N, T, P, S), symbol S ∈ / N1 ∪ N2 (noveˇ prˇidany´), T = T1 ∪ T2 , N = N1 ∪ N2 ∪ {S}, P = P1 ∪ P2 ∪ {S → S1 | S2 } Prˇejı´ma´me zde vsˇe z pu˚vodnıćh gramatik, zmeˇna je jen na zacˇa´tku derivace – prvnı´m krokem derivace je rozhodnutı´, zda bude generovańo slovo z prvnı´ho nebo z druhe´ho jazyka. Pak je provedena simulace cˇinnosti neˇktere´ z pu˚vodnıćh gramatik (resp. je prˇedańo rˇ´ızenı´ neˇktere´ z pu˚vodnıćh gramatik). 2 Prˇı´klad 1.14 Jazyk L9 = {ai bj ck | i, j, k ≥ 1, i = j nebo j = k} lze napsat jako sjednocenı´ dvou bezkontextovyćh jazyku˚ Lx ∪ Ly , kde Lx = {ai bj ck | i, j, k ≥ 1, i = j} Ly = {ai bj ck | i, j, k ≥ 1, j = k} (gramatiky viz prˇ´ıklad 1.16 na straneˇ 17)

✎ "


16

✎

Veˇta 1.8 Trˇ´ıda bezkontextovyćh jazyku˚ je uzavrˇena vzhledem k operaci zrˇeteˇzenı´. Du˚kaz: Vytvorˇ´ıme gramatiku G takovou, zˇe L(G) = L1 · L2 : N = N1 ∪ N2 ∪ {S}, S ∈ / N1 ∪ N2 P = P1 ∪ P2 ∪ {S → S1 · S2 } T = T1 ∪ T2 }

" 2

Veˇta 1.9 Trˇ´ıda bezkontextovyćh jazyku˚ je uzavrˇena vzhledem k operaci iterace (Kleeneho uza´veˇru, operace hveˇzdicˇka).

✎

Du˚kaz: Vytvorˇ´ıme gramatiku G takovou, zˇe L(G) = L∗1 : N = N1 ∪ {S}, S ∈ / N1 , T = T1 , P = P1 ∪ {S → S1 S | ε}

" 2

1.3.2 Operace, vzhledem k nimzˇ je jesˇteˇ trˇı´da L (CF ) uzavrˇena Veˇta 1.10 Trˇ´ıda bezkontextovyćh jazyku˚ je uzavrˇena vzhledem k operaci pozitivnı´ iterace. Du˚kaz: Vytvorˇ´ıme gramatiku G takovou, zˇe L(G) = N = N1 ∪ {S}, S ∈ / N1 , T = T1 , P = P1 ∪ {S → S1 S | S1 }

✎

L+ 1:

" 2

Veˇta 1.11 Trˇ´ıda bezkontextovyćh jazyku˚ je uzavrˇena vzhledem k operaci zrcadlenı´ (reverze). Du˚kaz: Vytvorˇ´ıme gramatiku G takovou, zˇe L(G) = LR 1: N = N1 , T = T1 , S = S1 Kazˇde´ pravidlo z pu˚vodnı´ mnozˇiny pravidel prˇevra´tı´me – prˇeneseme reverzi na pravidla: P = {A → αR | (A → α) ∈ P1 , A ∈ N1 , α ∈ (N ∪ T )∗ } 2 Prˇı´klad 1.15 Pravidlo A → abbBcaCacb bude po reverzi A → bcaCacBbba.

✎ "


17

Prˇı´klad 1.16 Reverzi si uka´zˇeme na tomto jazyce: L9 = {ai bj ck | i, j, k ≥ 1, i = j nebo j = k} Jazyk L9 lze generovat bezkontextovou gramatikou s pravidly S → S1 | S2 S1 → AX S2 → Y B

A → aAb | ab B → bBc | bc

X → cX | c Y → aY | a

Uka´zka derivace: S ⇒ S1 ⇒ AX ⇒ aAbX ⇒ aabbX ⇒ aabbc Po reverzi: S → S1 | S2 S1 → XA S2 → BY

A → bAa | ba B → cBb | cb

X → Xc | c Y →Ya|a

Uka´zka derivace: S ⇒ S1 ⇒ XA ⇒ XbAa ⇒ Xbbaa ⇒ cbbaa k j i Generovany´ jazyk je LR ˇ jako 9 = {c b a | i, j, k ≥ 1, i = j nebo j = k} a stejne pu˚vodnı´ jazyk, i tento je bezkontextovy´ (existuje bezkontextova´ gramatika, ktera´ ho generuje).

Veˇta 1.12 Trˇ´ıda bezkontextovyćh jazyku˚ je uzavrˇena vzhledem k operaci bezkontextove´ substituce. Du˚kaz: Bezkontextova´ substituce s je takove´ zobrazenı´, ktere´ zobrazuje kazˇdy´ symbol pu˚vodnı´ abecedy na bezkontextovy´ jazyk a prˇitom platı´ s(ε) = ε, s(a · v) = s(a) · s(v), a ∈ (N ∪ T ), v ∈ (N ∪ T )∗ Necht’L1 je bezkontextovy´ jazyk nad abecedou Σ = {a1 , a2 , . . . , an } a jsou dańy bezkontextove´ jazyky J1 , J2 , . . . , Jn nad abecedami Σ1 , Σ2 , . . . , Σn tak, zˇe s(ai ) = Ji , v kazˇde´m jazyce Si je startovacı´m symbolem ai , 1 ≤ i ≤ n. Pro vsˇechny bezkontextove´ jazyky Ji existujı´ bezkontextove´ gramatiky GJi = (NJi , Σi , PJi , ai ) a prˇedpokla´dejme, zˇe mnozˇiny jejich netermina´lnıćh symbolu˚ jsou po dvou disjunktnı´ a takte´zˇ pru˚nik ktere´koliv z teˇchto mnozˇin netermina´lu˚ s mnozˇinou N1 je pra´zdny´. Jazyk L = s(L1 ) sestrojı´me takto: S N = N1 ∪ {a1 , a2 , . . . , an } ∪ ni=1 NJi

✎ "


18

S T = ni=1 Σi S P = P1 ∪ ni=1 PJi

2

Prˇı´klad 1.17 Postup si uka´zˇeme na bezkontextove´m jazyku L9 = {ai bj ck | i, j, k ≥ 1, i = j nebo j = k}

G1 = ({S, A, B, X, Y }, {a, b, c}, P1 , S) a v mnozˇineˇ P1 jsou pravidla S → AX | Y B A → aAb | ab X → cX | c B → bBc | bc Y → aY | a Substituce: s(a) = {1n | n ≥ 0}, GJa = ({a}, {1}, {a → 1a | ε}, a) n n s(b) = {1 0 | n ≥ 1}, GJb = ({b}, {1, 0}, {b → 1b0 | 10}, b) s(c) = {0n | n ≥ 0}, GJc = ({c}, {0}, {c → 0c | ε}, c) Po provedenı´ substituce: G = ({S, A, B, X, Y, a, b, c}, {0, 1}, P, S) a v mnozˇineˇ P1 jsou pravidla S → AX | Y B X → cX | c a → 1a | ε A → aAb | ab Y → aY | a b → 1b0 | 10 B → bBc | bc c → 0c | ε Generovany´ jazyk je L = s(L9 ) = 1∗ · {1n 0n | n ≥ 1}∗ · 0∗

Pozna´mka: Protozˇe homomorfismus je vlastneˇ specia´lnı´m prˇ´ıpadem substituce (jde o jednoznacˇnou substituci, kdy jednomu symbolu prˇirˇazujeme pra´veˇ jedno slovo, tedy jednoprvkovy´ jazyk), znamena´ to, zˇe trˇ´ıda bezkontextovyćh jazyku˚ je uzavrˇena i vzhledem k operaci homomorfismu.

❁

1.3.3 Operace, vzhledem k nimzˇ trˇı´da L (CF ) nenı´ uzavrˇena Veˇta 1.13 Trˇ´ıda bezkontextovyćh jazyku˚ nenı´ uzavrˇena vzhledem k operaci pru˚niku. Du˚kaz: Najdeme dva bezkontextove´ jazyky, jejichzˇ pru˚nikem je jazyk, ktery´ nenı´ bezkontextovy´. Lx = {ai bi cj | i, j ≥ 0} (pocˇet a je stejny´ jako pocˇet b) Ly = {ai bk ck | i, j ≥ 0} (pocˇet b je stejny´ jako pocˇet c)

✎ "


19

Pru˚nikem teˇchto jazyku˚ je L = Lx ∩ Ly = L2 = {an bn cn | n ≥ 0}, o ktere´m jsme jizˇ drˇ´ıve doka´zali, zˇe nenı´ bezkontextovy´ (v prˇ´ıkladech 1.2 na straneˇ 7 a 1.13 na straneˇ 14). Vsˇimneˇme si, zˇe sjednocenı´m teˇchto jazyku˚ je bezkontextovy´ jazyk L9 ∪ {ε} = {ai bj ck | i, j, k ≥ 0, i = j nebo j = k}. 2 Veˇta 1.14 Trˇ´ıda bezkontextovyćh jazyku˚ nenı´ uzavrˇena vzhledem k operaci doplnˇku (komplementu) nad danou abecedou. Du˚kaz: Vyuzˇijeme jizˇ doka´zana´ tvrzenı´ z prˇedchozıćh veˇt, konkre´tneˇ to, zˇe trˇ´ıda bezkontextovyćh jazyku˚ je uzavrˇena vzhledem ke sjednocenı´, ale nenı´ uzavrˇena vzhledem k pru˚niku. Podle DeMorganovyćh pravidel, ktera´ si jisteˇ pamatujeme z teorie mnozˇin nebo algebry (jazyky vlastneˇ nejsou nic jine´ho nezˇ mnozˇiny slov), platı´ L1 ∩ L2 = L1 ∪ L2

✎ "

(1.4)

Prˇedpokla´dejme, zˇe trˇ´ıda bezkontextovyćh jazyku˚ je uzavrˇena vzhledem k operaci doplnˇku (du˚kaz sporem). Pak na prave´ straneˇ rovnice (1.4) ma´me mnozˇinu bezkontextovyćh jazyku˚. Jenzˇe na leve´ straneˇ rovnice je mnozˇina, ve ktere´ existujı´ i jazyky, ktere´ nejsou bezkontextove´ (pru˚nikem dvou bezkontextovyćh jazyku˚ mu˚zˇe by´t i jazyk, ktery´ nenı´ bezkontextovy´), cozˇ je spor. 2

1.4

Uza´veˇrove´ vlastnosti jako krite´rium bezkontextovosti

Veˇtsˇina uza´veˇrovyćh vlastnostı´ se da´ pouzˇ´ıt v prˇ´ıme´m du˚kazu: Prˇı´klad 1.18 Zjistı´me, zda je na´sledujıćı´ jazyk bezkontextovy´: L13 = {an1 bn1 an2 bn2 . . . ank bnk | k ≥ 0, ni ≥ 1, 1 ≤ i ≤ k} Vı´me, zˇe jazyk L1 = {an bn | n ≥ 1} je bezkontextovy´, a je zrˇejme´, zˇe L13 = L∗1 a proto i jazyk L13 je bezkontextovy´.


20

Nesmı´me zapomenout, zˇe vlastneˇ ani uza´veˇrove´ vlastnosti nejsou ekvivalence, ale pouze implikace (jestlizˇe L1 a L2 jsou bezkontextove´, pak . . . ). Du˚sledky mu˚zˇeme videˇt na prˇ´ıkladu Prˇı´klad 1.19 n o 2 Vı´me, zˇe jazyk L3 = an n ≥ 0 nenı´ bezkontextovy´ (to jsme doka´zali v prˇ´ıkladu 1.3 na straneˇ 7 pomocı´ Pumping lemma). Zvolı´me na´sledujıćı´ bezkontextovou (dokonce regula´rnı´) substituci: s(a) = b∗ Po uplatneˇnı´ substituce dostaneme jazyk {bi | i ≥ 0}, cozˇ je bezkontextovy´ (dokonce regula´rnı´) jazyk. Proto nenı´ pravda, zˇe kdyzˇ je vy´sledkem operace bezkontextovy´ jazyk, tak by operandy operace meˇly by´t take´.

Kapitola

2

Za´sobnı´kovy´ automat V te´to kapitole se podı´va´me na vlastnosti za´sobnı´kove´ho automatu, ktery´ jsme si strucˇneˇ popsali jizˇ na zacˇa´tku kurzu Teorie jazyku˚ a automatu˚ I. Tento typ automatu si definujeme, podı´va´me se na jeho typy a budeme se zaby´vat vztahem za´sobnı´kovyćh automatu˚ k bezkontextovy´m jazyku˚m a take´ deterministickou variantou.

2.1

Definice za´sobnı´kove´ho automatu

Za´sobnı´kovy´ automat dostaneme tak, zˇe konecˇny´ automat obohatı´me o za´sobnı´kovou pa´sku a zajistı´me, aby vy´pocˇet byl rˇ´ızen prˇedevsˇ´ım podle te´to za´sobnı´kove´ pa´sky. Za´sobnı´kovy´ automat pracuje takto: • vyjme symbol na vrcholu za´sobnı´ku, • mu˚zˇe nebo nemusı´ prˇecˇ´ıst jeden symbol ze vstupnı´ pa´sky, pokud prˇecˇte, posune se o polıćˇko da´l, • da´le se rozhoduje podle – sve´ho vnitrˇnı´ho stavu, – symbolu, ktery´ vyndal ze za´sobnı´ku, – pokud cˇetl ze vstupnı´ pa´sky, pak i podle prˇecˇtene´ho symbolu, • akce automatu spocˇ´ıva´ v prˇechodu do neˇktere´ho dalsˇ´ıho stavu a v ulozˇenı´ rˇeteˇzce znaku˚ do za´sobnı´ku. 21

KAPITOLA 2 ZA´SOBNI´KOVY´ AUTOMAT

22

Definice 2.1 (Za´sobnı´kovy´ automat) Za´sobnı´kovy´ automat je definovań jako A = (Q, Σ, Γ, δ, q0 , Z0 , F ), kde

✍

• Q je konecˇna´ nepra´zdna´ mnozˇina stavu˚, • Σ je konecˇna´ nepra´zdna´ abeceda, • Γ je konecˇna´ nepra´zdna´ za´sobnı´kova´ abeceda (symboly, ktere´ mohou by´t v za´sobnı´ku), • δ je prˇechodova´ funkce definovana´ nı´zˇe, • q0 je pocˇa´tecˇnı´ stav automatu, q0 ∈ Q, • Z0 je pocˇa´tecˇnı´ za´sobnı´kovy´ symbol, Z0 ∈ Γ, • F je mnozˇina koncovyćh stavu˚, F ⊆ Q (mu˚zˇe by´t i pra´zdna´). Prˇechodova´ funkce δ je zobrazenı´ δ : Q × (Σ ∪ {ε}) × Γ −→ Q × Γ∗ , lze zapsat take´ jako δ(qi , a, Z) 3 (qj , γ), qi , qj ∈ Q, a ∈ (Σ ∪ {ε}, Z ∈ Γ, γ ∈ Γ∗ . Za´sobnı´kovy´ automat je obecneˇ nedeterministicky´. Definice 2.2 (Konfigurace za´sobnı´kove´ho automatu) Konfigurace vy´sˇe definovane´ho za´sobnı´kove´ho automatu A je Q × Σ∗ × Γ∗ (take´ (q, α, γ), q ∈ Q, α ∈ Σ∗ , γ ∈ Γ∗ ). Pocˇa´tecˇnı´ konfigurace je (q0 , w, Z0 ), kde w je slovo, ktere´ bylo dańo na vstup automatu. Koncova´ konfigurace za´visı´ na typu za´sobnı´kove´ho automatu.

✍

Prvnı´ cˇlen konfigurace je stav, ve ktere´m se automat pra´veˇ nacha´zı´, druhy´ je neprˇecˇtena´ cˇa´st vstupnı´ pa´sky a trˇetı´ momenta´lnı´ obsah za´sobnı´ku. Definice 2.3 (Prˇechod mezi konfiguracemi) Prˇechod mezi konfiguracemi za´sobnı´kove´ho automatu je relace (qi , aα, Zβ) ` (qj , α, γβ)

⇐⇒

(qj , β) ∈ δ(qi , a, Z)

kde a ∈ Σ ∪ {ε}, Z ∈ Γ ∪ {ε}, α ∈ Σ∗ Symbol `∗ znacˇ´ı reflexivnı´ tranzitivnı´ uza´veˇr relace `∗ , symbol `+ je tranzitivnı´ uza´veˇr te´to relace (jaky´koliv pocˇet prˇechodu˚, alesponˇ jeden), symbol ì znamena´ prˇesneˇ i prˇechodu˚ mezi konfiguracemi.

✍


23

Definice 2.4 (Za´kladnı´ typy za´sobnı´kovyćh automatu˚) Rozezna´va´me tyto za´kladnı´ typy za´sobnı´kovyćh automatu˚: Za´sobnı´kovy´ automat koncˇ´ıcı´ prˇechodem do koncove´ho stavu je AF s koncovou konfiguracı´ (qf , ε, γ), qf ∈ F, γ ∈ Γ∗ a rozpozna´vany´ jazyk je L(AF ) = {w ∈ Σ∗ | (q0 , w, Z0 ) `∗ (qf , ε, γ), qf ∈ F, γ ∈ Γ∗ } Za´sobnı´kovy´ automat koncˇ´ıcı´ s pra´zdny´m za´sobnı´kem je A∅ s koncovou konfiguracı´ (q, ε, ε), q ∈ Q a rozpozna´vany´ jazyk je L(A∅ ) = {w ∈ Σ∗ | (q0 , w, Z0 ) `∗ (q, ε, ε), q ∈ Q} Za´sobnı´kovy´ automat koncˇ´ıcı´ prˇechodem do koncove´ho stavu a pra´zdny´m za´sobnı´kem je AF,∅ s koncovou konfiguracı´ (qf , ε, ε), qf ∈ F a rozpozna´vany´ jazyk je L(AF,∅ ) = {w ∈ Σ∗ | (q0 , w, Z0 ) `∗ (qf , ε, ε), qf ∈ F } Jak vidı´me, tyto trˇi za´kladnı´ typy se lisˇ´ı prˇedevsˇ´ım svou koncovou konfiguracı´: • za´sobnı´kovy´ automat koncˇ´ıcı´ v koncove´m stavu ukoncˇ´ı vy´pocˇet ve chvı´li, kdy ma´ prˇecˇtenou celou vstupnı´ pa´sku (prostrˇednı´ cˇlen konfigurace je ε) a nacha´zı´ se v neˇktere´m koncove´m stavu, • za´sobnı´kovy´ automat koncˇ´ıcı´ s pra´zdny´m za´sobnı´kem koncˇ´ı vy´pocˇet, kdyzˇ ma´ prˇecˇtenou celou vstupnı´ pa´sku a za´rovenˇ je pra´zdny´ za´sobnı´k, • trˇetı´ typ je kombinacı´ (pru˚nikem) obou prˇedchozıćh – musı´ by´t splneˇny obeˇ podmıńky. Vsˇechny trˇi typy za´sobnı´kovyćh automatu˚ koncˇ´ı samozrˇejmeˇ vy´pocˇet i tehdy, kdyzˇ nejsou v zˇa´dne´ koncove´ konfiguraci, ale do zˇa´dne´ dalsˇ´ı se nemohou dostat (prˇechodova´ funkce neda´va´ mozˇnost reagovat v dane´m stavu s dany´m obsahem za´sobnı´ku a vstupnı´ pa´sky).

✍


24

Prˇı´klad 2.1 Sestrojte za´sobnı´kovy´ automat (da´le ZA) koncˇ´ıcı´ s pra´zdny´m za´sobnı´kem rozpozna´vajıćı´ jazyk L14 = wcwR | w ∈ {a, b}∗ Vytvorˇ´ıme za´sobnı´kovy´ automat rozpozna´vajıćı´ pra´zdny´m za´sobnı´kem: A∅ = ({q0 , q1 }, {a, b}, {a, b, Z0 }, q0 , Z0 , δ, ∅) Automat bude pracovat takto: • v prvnı´ fa´zi bude cˇ´ıst obsah vstupu (prvnı´ polovina slova) a ukla´dat do za´sobnı´ku (vzˇdy co v kazˇde´m kroku vyjmeme, vra´tı´me do za´sobnı´ku za´rovenˇ se symbolem ze vstupu, tedy ukla´da´me dva symboly), jsme ve stavu q0 , • dı´ky principu za´sobnı´ku (cˇteme v opacˇne´m porˇadı´, nezˇ jak byly symboly ulozˇeny) je ukla´dana´ prvnı´ polovina slova za´rovenˇ zrcadloveˇ prˇevraćena, • kdyzˇ na vstupu narazı´me na c (hranice, polovina slova), prˇejdeme do stavu q1 a tı´m zmeˇnı´me zpu˚sob praće automatu, • kdyzˇ jsme ve stavu q1 , nic do za´sobnı´ku neukla´da´me, symbol, ktery´ v kazˇde´m kroku vyjmeme, porovna´me s tı´m, co je na vstupu – kdyzˇ souhlası´, mu˚zˇeme pokracˇovat (tj. v kazˇde´m kroku se posuneme na vstupu a za´rovenˇ ubereme symbol ze za´sobnı´ku). δ(q0 , a, Z0 ) = (q0 , aZ0 ) δ(q0 , b, Z0 ) = (q0 , bZ0 ) δ(q0 , a, X) = (q0 , aX), X ∈ {a, b} δ(q0 , c, X) = (q1 , X), X ∈ {a, b} δ(q1 , a, a) = (q1 , ε) δ(q1 , b, b) = (q1 , ε) δ(q1 , ε, Z0 ) = (q1 , ε)

na zacˇa´tku vy´pocˇtu, slovo zacˇ´ına´ a na zacˇa´tku vy´pocˇtu, slovo zacˇ´ına´ b zatı´m jen nacˇ´ıta´me a ukla´da´me do za´sobnı´ku jsme na hranici shoda a v obou polovinaćh slova shoda b v obou polovinaćh slova skoncˇili jsme na vstupu i v za´sobnı´ku

Uka´zka vy´pocˇtu automatu na slovo abcba: (q0 , abcba, Z0 ) ` (q0 , bcba, aZ0 ) ` ` (q0 , cba, baZ0 ) ` ` (q1 , ba, baZ0 ) ` (q1 , a, aZ0 ) ` ` (q1 , ε, Z0 ) ` (q1 , ε, ε)

q0 : prˇena´sˇ´ıme do za´sobnı´ku obsah vstupu hranicˇnı´ bod, prˇejdeme do mo´du q1 q1 : jen vybı´ra´me ze za´sobnı´ku a porovna´va´me konec


25

Pozna´mka: Za´sobnı´kovy´ automat koncˇ´ıcı´ v koncove´m stavu (a vlastneˇ i „hybridnı´“ typ) bychom z prˇedesˇle´ho vytvorˇili jednodusˇe – stacˇ´ı poslednı´ cˇa´st definice δ funkce prˇepsat takto: δ(q1 , ε, Z0 ) = (q2 , ε) s tı´m, zˇe Q = {q0 , q1 , q2 }, F = {q2 }. Prˇı´klad 2.2 Vytvorˇte za´sobnı´kovy´ automat koncˇ´ıcı´ v koncove´m stavu reprezentovany´ stavovy´m diagramem pro jazyk z prˇ´ıkladu 2.1 L14 = wcwR | w ∈ {a, b}∗ .

Narozdı´l od konecˇnyćh automatu˚, u za´sobnı´kovyćh na´m nestacˇ´ı ohodnotit sˇipky pouze symbolem nacˇ´ıtany´m ze vstupnı´ pa´sky. Musı´me vzˇdy zadat trˇi u´daje (ve spra´vne´m porˇadı´!) • symbol nacˇteny´ ze vstupu (nebo ε, kdyl’ ze vstupu nic nenacˇ´ıta´me), • symbol, ktery´ vyjı´ma´me ze za´sobnı´ku (nesmı´ zde by´t ε!, v kal’de´m kroku musı´me neˇjaky´ symbol vyndat), • rˇeteˇzec, ktery´ ukla´da´me do za´sobnı´ku. Diagram vytvorˇ´ıme podle δ funkce v prˇ´ıkladu 2.1, jen navıć zakomponujeme zmeˇnu zahrnutou v pozna´mce nad tı´mto prˇ´ıkladem. Vy´sledny´ diagram vidı´me na obra´zku 2.1. a, X, aX b, X, bX

q0

c, X, X

a, a, ε b, b, ε

q1

ε, Z0 , ε

q2

X ∈ {a, b, Z0 }

Obra´zek 2.1: Diagram za´sobnı´kove´ho automatu

2.2

Vztah mezi ru˚zny´mi typy za´sobnı´kovyćh automatu˚

Zde se podı´va´me na vztahy mezi trˇ´ıdami jazyku˚ generovanyćh za´sobnı´kovy´mi automaty koncˇ´ıcı´mi v koncove´m stavu, pra´zdny´m za´sobnı´kem a nebo obojı´m.

❁


26

V dalsˇ´ım textu budeme pouzˇ´ıvat toto oznacˇenı´: LF = {L | L = L(AF ) pro neˇjaky´ za´sobnı´kovy´ automat AF } . . . . . . . . . . . . . . . . . . . Trˇ´ıda jazyku˚ generovanyćh ZA koncˇ´ıcı´mi v koncove´m stavu L∅ = {L | L = L(A∅ ) pro neˇjaky´ za´sobnı´kovy´ automat A∅ } . . . . . . . . . . . . . . Trˇ´ıda jazyku˚ generovanyćh ZA koncˇ´ıcı´mi pra´zdny´m za´sobnı´kem LF,∅ = {L | L = L(AF,∅ ) pro neˇjaky´ za´sobnı´kovy´ automat AF } . . . . . . Trˇ´ıda jazyku˚ generovanyćh ZA koncˇ´ıcı´mi v koncove´m stavu s pra´zdny´m za´sobnı´kem Veˇta 2.1 Necht’ A = (Q, Σ, Γ, q0 , Z0 , δ, ∅) je ZA koncˇ´ıcı´ vy´pocˇet pra´zdny´m za´sobnı´kem. Potom existuje ZA A0 = (Q0 , Σ, Γ0 , q00 , Z00 , δ 0 , F ) koncˇ´ıcı´ vy´pocˇet v koncove´m stavu takovy´, zˇe L(A0 ) = L(A). To znamena´, zˇe pro trˇ´ıdy jazyku˚ generovanyćh jednotlivy´mi typy ZA platı´ relace L∅ ⊆ LF (2.1)

✎

Du˚kaz: Budeme postupovat takto: • do za´sobnı´ku da´me pomocnou „zara´zˇku“ (pocˇa´tecˇnı´ za´sobnı´kovy´ symbol pu˚vodnı´ho automatu Z0 ) a da´le budeme simulovat vy´pocˇet pu˚vodnı´ho automatu, • simulovany´ vy´pocˇet probı´ha´ nad vlozˇenou „zara´zˇkou“ a koncˇ´ı ve chvı´li, kdy je tato zara´zˇka vyjmuta (v te´ chvı´li ma´ simulovany´ automat pra´zdny´ za´sobnı´k), v za´sobnı´ku je pouze Z00 (pocˇa´tecˇnı´ za´sobnı´kovy´ symbol nove´ho automatu), • pak jen prˇejdeme do koncove´ho stavu; pokud je cela´ vstupnı´ pa´ska prˇecˇtena´, pak koncˇ´ı vy´pocˇet s u´speˇchem, slovo je prˇijato. Q0 = Q ∪ {q00 , qf }, q00 ∈ / Q, qf ∈ /Q F = {qf } Γ0 = Γ ∪ {Z00 } Funkci δ 0 definujeme takto: • na zacˇa´tku vy´pocˇtu prˇida´me do za´sobnı´ku pocˇa´tecˇnı´ za´sobnı´kovy´ symbol pu˚vodnı´ho automatu, abychom mu pro simulaci prˇipravili vhodne´ pracovnı´ prostrˇedı´: δ 0 (q00 , ε, Z00 ) = (q0 , Z0 Z00 )

"


27

• potom simulujeme cˇinnost pu˚vodnı´ho automatu (tj. prˇejmeme chovańı´ jeho δ funkce): δ 0 (q, a, Z) = δ(q, a, Z) ∀q ∈ Q, a ∈ Σ ∪ {ε}, Z ∈ Γ • po ukoncˇenı´ vy´pocˇtu pu˚vodnı´ho automatu prˇejdeme do koncove´ho stavu: δ 0 (q, ε, Z00 ) = (qf , ε) Prˇechod mezi konfiguracemi bude na´sledujıćı´: ` (q0 , w, Z0 Z00 ) ` . . . pu˚vodnı´ vy´pocˇet . . . ` (q, ε, Z00 ) ` (qf , ε, ε)

(q00 , w, Z00 )

2

Veˇta 2.2 Necht’ A = (Q, Σ, Γ, q0 , Z0 , δ, F ) je ZA koncˇ´ıcı´ vy´pocˇet v neˇktere´m koncove´m stavu. Potom existuje ZA A0 = (Q0 , Σ, Γ0 , q00 , Z00 , δ 0 , ∅) koncˇ´ıcı´ vy´pocˇet pra´zdny´m za´sobnı´kem takovy´, zˇe L(A0 ) = L(A). To znamena´, zˇe pro trˇ´ıdy jazyku˚ generovanyćh jednotlivy´mi typy ZA platı´ relace LF ⊆ L∅ (2.2) Du˚kaz: Abychom se v pru˚beˇhu vy´pocˇtu „na´hodou“ nedostali na dno a tak prˇedcˇasneˇ neukoncˇili vy´pocˇet, tak stejneˇ jako v prˇedchozı´m du˚kazu do za´sobnı´ku da´me pomocnou „zara´zˇku“ (pocˇa´tecˇnı´ za´sobnı´kovy´ symbol pu˚vodnı´ho automatu Z0 ) a da´le budeme simulovat vy´pocˇet pu˚vodnı´ho automatu. Nejdrˇ´ıv si definujeme funkci δ 0 : • na zacˇa´tku vy´pocˇtu prˇida´me do za´sobnı´ku pocˇa´tecˇnı´ za´sobnı´kovy´ symbol pu˚vodnı´ho automatu: δ 0 (q00 , ε, Z00 ) = (q0 , Z0 Z00 ) • potom simulujeme cˇinnost pu˚vodnı´ho automatu: δ 0 (q, a, Z) = δ(q, a, Z) ∀q ∈ Q, a ∈ Σ ∪ {ε}, Z ∈ Γ • po ukoncˇenı´ vy´pocˇtu pu˚vodnı´ho automatu vypra´zdnı´me za´sobnı´k, ale nesmı´me zapomenout na to, zˇe simulovany´ automat by v koncove´m stavu jesˇteˇ mohl chtı´t pracovat (stav, ve ktere´m bude mazań za´sobnı´k, je d – delete): δ 0 (qf , ε, Z) = δ(qf , ε, Z) ∪ {(d, ε)} δ 0 (d, ε, Z) = (d, ε), ∀Z ∈ Γ0 Q0 = Q ∪ {q00 , d}, q00 ∈ / Q, d ∈ / Q, Γ0 = Γ ∪ {Z00 } Prˇechod mezi konfiguracemi bude na´sledujıćı´: (q00 , w, Z00 ) ` (q0 , w, Z0 Z00 ) ` . . . pu˚vodnı´ vy´pocˇet . . . ` (qf , ε, ZαZ00 ) ` ` (d, ε, αZ00 ) ` . . . ` (d, ε, ε)

2

✎

"


28

Du˚sledek 2.3 Trˇ´ıdy jazyku˚ generovanyćh za´sobnı´kovy´mi automaty koncˇ´ıcı´mi v koncove´m stavu a za´sobnı´kovy´mi automaty koncˇ´ıcı´mi s pra´zdny´m za´sobnı´kem jsou ekvivalentnı´: LF = L∅

➠

(2.3)

Da´le z vlastnostı´ za´sobnı´kovyćh automatu˚ generujıćıćh jazyky z trˇ´ıdy LF,∅ plyne, zˇe LF,∅ = L∅ = LF

(2.4)

Mnozˇinu vsˇech za´sobnı´kovyćh automatu˚ budeme souhrnneˇ oznacˇovat ZA, trˇ´ıdu (mnozˇinu) jazyku˚ rozpozna´vanyćh za´sobnı´kovy´mi automaty L (ZA).

2.3

Vztah za´sobnı´kovyćh automatu˚ a bezkontextovyćh jazyku˚

Nada´le budeme pocˇ´ıtat s tı´m, zˇe za´sobnı´kove´ automaty vsˇech trˇ´ı za´kladnıćh typu˚ jsou navza´jem ekvivalentnı´, a tedy generujı´ stejne´ trˇ´ıdy jazyku˚. Proto v du˚kazech budeme volneˇ tyto typy zameˇnˇovat. Veˇta 2.4 Ke kazˇde´ bezkontextove´ gramatice G lze vytvorˇit za´sobnı´kovy´ automat A takovy´, zˇe L(G) = L(A), tedy L (CF ) ⊆ L (ZA) (2.5) Du˚kaz: Ma´me bezkontextovou gramatiku G = (N, T, P, S) a chceme sestrojit za´sobnı´kovy´ automat A = (Q, Σ, Γ, q0 , Z0 , δ, ∅) (automat koncˇ´ı s pra´zdny´m za´sobnı´kem). Budeme postupovat takto: • v za´sobnı´ku mohou by´t netermina´ly a termina´ly, ze kteryćh se skla´dajı´ pravidla, prave´ strany pravidel ukla´da´me do za´sobnı´ku, • pokud je na vrcholu za´sobnı´ku netermina´l, vyjmeme ho a nahradı´me pravou stranou neˇktere´ho pravidla prˇepisujıćı´ho tento netermina´l, • pokud ze za´sobnı´ku vyjme termina´lnı´ symbol, nacˇte symbol ze vstupu a porovna´ – pokud jsou stejne´, mu˚zˇe da´l pokracˇovat (do za´sobnı´ku uzˇ vyjmuty´ symbol nevracı´, a na vstupu se prˇi prˇecˇtenı´ vstupnı´ho symbolu posune na dalsˇ´ı).

"


29

Q = {q}, q0 = q, Σ = T (termina´lnı´ symboly pouzˇijeme pro abecedu), Γ = N ∪T, Z0 = S (startovacı´ symbol pouzˇijeme jako pocˇa´tecˇnı´ symbol za´sobnı´ku). Pro kazˇde´ pravidlo A → α vytvorˇ´ıme δ(q, ε, A) 3 (q, α) (ze za´sobnı´ku vyjmeme A a nahradı´me ho rˇeteˇzcem α) Pro kazˇdy´ termina´lnı´ symbol a ∈ T vytvorˇ´ıme δ(q, a, a) = (q, ε, ε) (tenty´zˇ symbol vynda´me ze za´sobnı´ku i prˇecˇteme ze vstupu). Shrnˇme si celou δ funkci: δ(q, ε, A) = {(q, α) | (A → α) ∈ P } δ(q, a, a) = {(q, ε)} , ∀a ∈ T Vytvorˇeny´ za´sobnı´kovy´ automat je nedeterministicky´, protozˇe v gramatice je obvykle vıće pravidel pro stejny´ netermina´lnı´ symbol. Automat jednodusˇe simuluje odvozovańı´ v gramatice – na za´sobnı´ku prova´dı´ „odvozovańı´“ stejneˇ, jako bychom v gramatice prˇepisovali postupneˇ netermina´ly v prˇepisovane´m sloveˇ zleva. 2 Prˇı´klad 2.3 G = ({S}, {a, b, c}, P, S), kde P = {S → aSa | bSb | c} Tato gramatika generuje na´m jizˇ zna´my´ jazyk L14 = wcwR | w ∈ {a, b}∗ Vytvorˇ´ıme za´sobnı´kovy´ automat A = ({q}, {a, b, c}, {S, a, b, c}, q, S, ∅) generujıćı´ tento jazyk. δ(q, ε, S) = {(q, aSa), (q, bSb), (q, c)} δ(q, a, a) = {(q, ε)} δ(q, b, b) = {(q, ε)} Uka´zka rozpoznańı´ slova abcba:

(q, abcba, S) ` (q, abcba, aSa) ` (q, bcba, Sa) ` (q, bcba, bSba) ` (q, cba, Sba) ` ` (q, cba, cba) ` (q, ba, ba) ` (q, a, a) ` (q, ε, ε) Uka´zka neu´speˇsˇne´ho vy´pocˇtu (slovo acb bude odmı´tnuto): (q, acb, S) ` (q, acb, aSa) ` (q, cb, Sa) ` (q, cb, ca) ` (q, b, a) ` ×

Na´sledujıćı´ veˇtu vyuzˇijeme v du˚kazu veˇty 2.6 na straneˇ 33. Veˇta 2.5 Ke kazˇde´mu za´sobnı´kove´mu automatu A existuje jednostavovy´ za´sobnı´kovy´ automat A0 takovy´, zˇe L(A0 ) = L(A).

✎


30

Du˚kaz: Pu˚vodnı´ a vytva´rˇeny´ automat jsou: A = (Q, Σ, Γ, δ, q0 , Z0 , ∅) A0 = ({s}, Σ, Γ0 , δ 0 , s, Z00 , ∅) Za´sobnı´kovy´ automat se v kazˇde´m kroku obvykle rozhoduje podle trˇ´ı krite´riı´ – stavu vstupnı´ pa´sky, stavu za´sobnı´ku a sve´ho vnitrˇnı´ho stavu, ale kdyzˇ ma´ k dispozici jen jediny´ vnitrˇnı´ stav, musı´ se umı´steˇnı´ te´to informace nahradit neˇcˇ´ım jiny´m. Vstupnı´ pa´sku nesmı´me pozmeˇnit, zby´va´ jen za´sobnı´k. Tedy informaci pu˚vodneˇ ulozˇenou ve vnitrˇnı´m stavu prˇesuneme do za´sobnı´ku tak, zˇe mı´sto „jednoduchyćh“ za´sobnı´kovyćh symbolu˚ budeme pouzˇ´ıvat usporˇa´dane´ trojice, jejichzˇ druhy´ prvek je neˇktery´ symbol pu˚vodnı´ za´sobnı´kove´ abecedy, prvnı´ a trˇetı´ prvek jsou stavy: n o Γ0 = [qi , Z, qj ] qi , qj ∈ Q, Z ∈ Γ • qi je stav, ve ktere´m je Z na vrcholu za´sobnı´ku pu˚vodnı´ho automatu (a tedy se v tom stavu vybı´ra´ ze za´sobnı´ku), • qj je stav, do ktere´ho prˇecha´zı´me prˇi vyjmutı´ vsˇeho, co mu˚zˇe by´t vygenerovańo pomocı´ Z, ze za´sobnı´ku v pu˚vodnı´m automatu. V za´sobnı´ku tedy kromeˇ pu˚vodnıćh za´sobnı´kovyćh symbolu˚ ukla´da´me take´ informaci o tom, v jake´m stavu jsou tyto symboly zpracova´vańy a do jake´ho stavu prˇecha´zı´me po jejich plne´m zpracovańı´ v pu˚vodnı´m automatu. Nynı´ definujeme prˇechodovou funkci: 1. Na zacˇa´tku vy´pocˇtu prˇipravı´me simulaci pu˚vodnı´ho automatu: n o δ 0 (s, ε, Z00 ) = s, [q0 , Z0 , p] p ∈ Q

2. Pro vsˇechny funkce automatu A ve tvaru δ(p, a, Z) 3 (q, ε) (do za´sobnı´ku nic nevkla´dajı´) vytvorˇ´ıme 0 δ s, a, [p, Z, q] 3 (s, ε), a ∈ Σ ∪ {ε} 3. Pro vsˇechny ostatnı´ funkce ve tvaru δ(p, a, Z) 3 (q, B1 B2 . . . Bn ): n 0 s, [q, B1 , u1 ][u1 , B2 , u2 ][u2 , B3 , u3 ] . . . [un−1 Bn un ] δ s, a, [p, Z, un ] ⊇ o ∀ kombinace stavu˚ ui ∈ Q, 1 ≤ i ≤ n, a ∈ Σ ∪ {ε}

"


31

Nejna´rocˇneˇjsˇ´ı je urcˇiteˇ poslednı´ bod. Nove´ za´sobnı´kove´ symboly zde urcˇujı´ vsˇechny mozˇne´ posloupnosti, jaky´mi lze v pu˚vodnı´m automatu dojı´t ze stavu q, ve ktere´m vybı´ra´me ze za´sobnı´ku symbol Z, do neˇktere´ho stavu un , do ktere´ho prˇecha´zı´me po zpracovańı´ poslednı´ho zde vkla´dane´ho symbolu, Bn . Musı´ zde by´t vsˇechny mozˇne´ kombinace n-tic pu˚vodnıćh stavu˚, protozˇe nemu˚zˇeme prˇedvı´dat, jaka´ posloupnost zpracova´vanyćh stavu˚ bude v teˇchto n krocıćh pouzˇita. Je zrˇejme´, zˇe symbol Z je vyjmut ve stavu p a hned prˇecha´zı´me do stavu q; za´rovenˇ vkla´da´me do za´sobnı´ku symboly B1 , B2 , . . . , Bn , a to pocˇ´ınaje symbolem Bn (symbol B1 pak bude na vrcholu za´sobnı´ku), proto ze stavu q po vyjmutı´ symbolu B1 prˇecha´zı´me do stavu u1 , atd. Azˇ zpracujeme vsˇe, co bylo vygenerovańo ze symbolu Z (tj. vsˇechny symboly B1 , . . . , Bn ), dostaneme se do stavu un . 2 Prˇı´klad 2.4 Postup uka´zˇeme na jazyku L15 = an c bn ck | n ≥ 0, k > 0

Tento jazyk rozpozna´va´ za´sobnı´kovy´ automat A = ({0, 1}, {a, b, c}, {Z0 , a}, δ, 0, Z0 , ∅) δ(0, a, X) = (0, aX), X ∈ {a, Z0 } δ(0, c, X) = (1, X), X ∈ {a, Z0 } δ(1, b, a) = (1, ε) δ(1, c, Z0 ) = {(1, Z0 ), (1, ε)} Vytvorˇ´ıme automat A0 : n o 0 0 δ s, ε, Z0 = s, [0, Z0 , 0] , s, [0, Z0 , 1] n o 0 δ s, a, [0, X, 0] = s, [0, a, 0][0, X, 0] , s, [0, a, 1][1, X, 0] , X ∈ {a, Z0 } n o δ 0 s, a, [0, X, 1] = s, [0, a, 0][0, X, 1] , s, [0, a, 1][1, X, 1] n o δ 0 s, c, [0, X, 0] = s, [1, X, 0] n o δ 0 s, c, [0, X, 1] = s, [1, X, 1] δ 0 s, b, [1, a, 1] = {(s, ε)} n o δ 0 s, c, [1, Z0 , 0] = s, [1, Z0 , 0] n o 0 δ s, c, [1, Z0 , 1] = s, [1, Z0 , 1] , (s, ε)


32

Nove´ za´sobnı´kove´ symboly jsou mozˇna´ prˇehledne´ z hlediska vytvorˇenı´, ale bude lepsˇ´ı nahradit je kratsˇ´ımi variantami podle na´sledujıćı´ tabulky. Dlouhe´ oznacˇenı´ −→Kra´tke´ oznacˇenı´ [0, Z0 , 0] [0, Z0 , 1] [1, Z0 , 0] [1, Z0 , 1] [0, a, 0] [0, a, 1] [1, a, 0] [1, a, 1]

−→ −→ −→ −→ −→ −→ −→ −→

A B C D E F G H

Upravı´me δ 0 funkci: δ 0 (s, ε, Z00 ) = {(s, A), (s, B)} δ 0 (s, a, A) = {(s, EA), (s, F C)} δ 0 (s, a, E) = {(s, EE), (s, F G)} δ 0 (s, a, B) = {(s, EB), (s, F D)} δ 0 (s, a, F ) = {(s, EF ), (s, F H)}

δ 0 (s, c, A) = {(s, C)} δ 0 (s, c, E) = {(s, G)} δ 0 (s, c, B) = {(s, D)} δ 0 (s, c, F ) = {(s, H)}

δ 0 (s, b, H) = {(s, ε)}

δ 0 (s, c, C) = {(s, C)} δ 0 (s, c, D) = {(s, D), (s, ε)}

Automat potom mu˚zˇeme urcˇit takto: A = ({s}, {a, b, c}, {Z00 , A, B, C, D, E, F, G, H}, δ 0 , s, Z00 , ∅) 0

Uka´zka rozpoznańı´ slova aacbbc automatem A: (0, aacbbc, Z0 ) ` (0, acbbc, aZ0 ) ` (0, cbbc, aaZ0 ) ` (1, bbc, aaZ0 ) ` (1, bc, aZ0 ) ` ` (1, c, Z0 ) ` (1, ε, ε) Uka´zka rozpoznańı´ slova aacbbc automatem A0 : (s, aacbbc, Z00 ) ` (s, aacbbc, B) ` (s, acbbc, F D) ` ` (s, cbbc, F HD) ` (s, bbc, HHD) ` (s, bc, HD) ` (s, c, D) ` (s, ε, ε) Tote´zˇ, ale bez nahrazenı´ za´sobnı´kovyćh symbolu˚ kratsˇ´ımi verzemi: (s, aacbbc, Z00 ) ` s, aacbbc, [0, Z0 , 1] ` s, acbbc, [0, a, 1][1, Z0 , 1] ` ` s, cbbc, [0, a, 1][1, a, 1][1, Z0 , 1] ` (s, bbc, [1, a, 1][1, a, 1][1, Z0 , 1] ` ` s, bc, [1, a, 1][1, Z0 , 1] ` s, c, [1, Z0 , 1] ` (s, ε, ε)


33

Veˇta 2.6 Ke kazˇde´mu za´sobnı´kove´mu automatu A existuje bezkontextova´ gramatika G takova´, zˇe L(G) = L(A), tedy L (ZA) ⊆ L (CF )

✎

(2.6)

Du˚kaz: Kdyzˇ jsme dokazovali, zˇe ke kazˇde´ bezkontextove´ gramatice lze sestrojit ekvivalentnı´ za´sobnı´kovy´ automat (v du˚kazu veˇty 2.4 na straneˇ 28), vytvorˇili jsme jednostavovy´ za´sobnı´kovy´ automat. Zde vyuzˇijeme prˇesneˇ opacˇny´ postup – podle jednostavove´ho automatu vytvorˇ´ıme gramatiku. Prvnı´m krokem tedy bude vytvorˇenı´ jednostavove´ho za´sobnı´kove´ho automatu 0 A k automatu A podle postupu popsane´ho v du˚kazu veˇty 2.5. V druhe´m kroku vytvorˇ´ıme gramatiku, jejı´zˇ netermina´ly vytvorˇ´ıme ze za´sobnı´kovyćh symbolu˚. Kdyzˇ oba kroky shrneme, postup je na´sledujıćı´:

"

1. Inicializujeme vy´pocˇet: ∀q ∈ Q :

S → [q0 , Z0 , q]

2. Pro vsˇechny funkce automatu A ve tvaru δ(p, a, Z) 3 (q, ε) (do za´sobnı´ku nic nevkla´dajı´) vytvorˇ´ıme [p, Z, q] → a 3. Pro vsˇechny ostatnı´ funkce ve tvaru δ(p, a, Z) 3 (q, B1 B2 . . . Bn ): [p, Z, un ] → a[q, B1 , u1 ][u1 , B2 , u2 ] . . . [un−1 , Bn , un ] pro kazˇdou kombinaci stavu˚ ui ∈ Q, 1 ≤ i ≤ n. 2 Prˇı´klad 2.5 Budeme pokracˇovat v prˇ´ıkladu 2.4 na straneˇ 31. V zadańı´ prˇ´ıkladu byl automat A = ({0, 1}, {a, b, c}, {Z0 , a}, δ, 0, Z0 , ∅) δ(0, a, X) = (0, aX), X ∈ {a, Z0 } δ(0, c, X) = (1, X), X ∈ {a, Z0 } δ(1, b, a) = (1, ε) δ(1, c, Z0 ) = {(1, Z0 ), (1, ε)}


34

Podle popsane´ho postupu vytvorˇ´ıme gramatiku G = (N, T, P, S), T = Σ, 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 , 1] 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[1, Z0 , 0] [0, a, 0] → c[1, a, 0] [0, Z0 , 1] → c[1, Z0 , 1] [0, a, 1] → c[1, a, 1] [1, a, 1] → b [1, Z0 , 0] → c[1, Z0 , 0] [1, Z0 , 1] → c[1, Z0 , 1] c

Zjednodusˇ´ıme netermina´ly a shrneme pravidla prˇepisujıćı´ stejny´ netermina´l:

S→A|B Odstranı´me nadbytecˇne´ symboly: A → aEA | aF C | cC S→B B → aEB | aF D | cD B → aF D | cD C → cC C → cC D → cD | c D → cD | c E → aEE | aF G | cG F → aF H | cH F → aEF | aF H | cH H→b H→b Netermina´ly: N = {S, B, C, D, F, H} Uka´zka generovańı´ slova aacbbc: S ⇒ B ⇒ aF D ⇒ aaF HD ⇒ aacHHD ⇒ aacbHD ⇒ aacbbD ⇒ ⇒ aacbbcD ⇒ aacbbcc Da´ se jednodusˇe doka´zat, zˇe generovany´ jazyk je L15 = an c bn ck | n ≥ 0, k > 0


35

Du˚sledkem veˇt 2.4 na straneˇ 28 a 2.6 na straneˇ 33 je ekvivalence trˇ´ıd jazyku˚: Du˚sledek 2.7 L (ZA) ' L (CF )

2.4

(2.7)

➠

Za´sobnı´kove´ automaty a uza´veˇrove´ vlastnosti bezkontextovyćh jazyku˚

V sekci 1.3 na straneˇ 15 jsme probrali te´meˇrˇ vsˇechny operace, vzhledem k nimzˇ je nebo nenı´ trˇ´ıda bezkontextovyćh jazyku˚ uzavrˇena, a doka´zali jsme (veˇta 1.13 na straneˇ 18), zˇe trˇ´ıda bezkontextovyćh jazyku˚ nenı´ uzavrˇena vzhledem k operaci pru˚niku. To vsˇak neplatı´ pro pru˚nik s regula´rnı´m jazykem: Veˇta 2.8 Trˇ´ıda bezkontextovyćh jazyku˚ je uzavrˇena vzhledem k pru˚niku s regula´rnı´m jazykem. Du˚kaz: Narozdı´l od jinyćh uza´veˇrovyćh vlastnostı´ bezkontextovyćh jazyku˚, zde konstrukci nebudeme prova´deˇt na gramatikaćh, ale na automatech. Postup bude podobny´ tomu, ktery´ jsme pouzˇili v kurzu Teorie jazyku˚ a automatu˚ I pro pru˚nik dvou regula´rnıćh jazyku˚. Vytva´rˇ´ıme pru˚nik bezkontextove´ho jazyka reprezentovane´ho za´sobnı´kovy´m automatem A1 a regula´rnı´ho jazyka reprezentovane´ho konecˇny´m automatem A2 : (1)

(1)

A1 = (Q1 , Σ1 , Γ1 , δ1 , q0 , Z0 , F1 ) (rozpozna´va´ koncovy´m stavem) (2) A2 = (Q2 , Σ2 , δ2 , q0 , F2 ) Sestrojı´me A = (Q, Σ, Γ, δ, q0 , Z0 , F ), L(A) = L(A1 ) ∩ L(A2 ). Je zrˇejme´, zˇe Σ = Σ1 ∪ Σ2 , Γ = Γ1 , Z0 = Z00 . Vy´pocˇet v automatu A ma´ by´t simultańnı´ simulacı´ obou pu˚vodnıćh automatu˚, slovo, ktere´ ma´ by´t rozpoznańo, prosteˇ za´rovenˇ da´me na vstup obou pu˚vodnıćh automatu˚ a prˇijmeme ho, pokud v obou automatech bude existovat vy´pocˇet od pocˇa´tecˇnı´ k neˇktere´ konecˇne´ konfiguraci. Stavy automatu A budou usporˇa´dane´ dvojice stavu˚ pu˚vodnıćh automatu˚, prvnı´ prvek je stav automatu A1 a druhy´ je stav automatu A2 . Usporˇa´dana´ dvojice zachycuje, v jake´m stavu v pu˚vodnıćh automatech je pra´veˇ simulovany´ vy´pocˇet. Q = {[q1 , q2 ] | q1 ∈ Q1 , q2 ∈ Q2 } Mnozˇina koncovyćh stavu˚: F = {[q1 , q2 ] | q1 ∈ F1 , q2 ∈ F2 } Definujeme δ funkci:

✎ "


36

1. V kazˇde´m kroku, ve ktere´m je cˇten symbol ze vstupu, se posouva´me v obou simulovanyćh automatech, v tom za´sobnı´kove´m take´ pracujeme se za´sobnı´kem – pro kazˇde´ a ∈ Σ, q1 , p1 ∈ Q1 , q2 , p2 ∈ Q2 , Z ∈ Γ, γ ∈ Γ∗1 : δ([q1 , q2 ], a, Z) 3 ([p1 , p2 ], γ)

⇐⇒

δ1 (q1 , a, Z) 3 (p1 , γ), δ2 (q2 , a) 3 p2

2. Vyrˇesˇ´ıme odlisˇnost pu˚vodnıćh automatu˚ prˇi praći se vstupnı´ abecedou. Za´sobnı´kovy´ automat nemusı´ v kazˇde´m kroku cˇ´ıst ze vstupnı´ pa´sky, kdezˇto konecˇny´ ano. Proto umozˇnı´me simulaci konecˇne´ho automatu deˇlat ε-kroky, prˇi kteryćh nebude cˇ´ıst ze vstupnı´ pa´sky ani prova´deˇt zmeˇnu stavu – pro kazˇde´ q1 , p1 ∈ Q1 , q2 ∈ Q2 , Z ∈ Γ, γ ∈ Γ∗1 : δ([q1 , q2 ], ε, Z) 3 ([p1 , q2 ], γ)

⇐⇒

δ1 (q1 , ε, Z) 3 (p1 , γ) 2

Prˇı´klad 2.6 Vezmeme bezkontextovy´ jazyk L16 = wwR | w ∈ {a, b}∗ a regula´rnı´ jazyk a∗ . Jejich pru˚nikem je jazyk L17 = {an an | n ≥ 0} = {a2n | n ≥ 0} Sestrojı´me automat A1 , L(A1 ) = L16 : A1 = ({q0 , q1 , q2 }, {a, b}, {Z0 , a, b}, δ1 , q0 , Z0 , {q2 }), kde δ1 (q0 , a, Z0 ) = {(q0 , aZ0 )} δ1 (q0 , b, Z0 ) = {(q0 , bZ0 )} δ1 (q0 , a, b) = {(q0 , ab)} δ1 (q0 , b, a) = {(q0 , ba)}

δ1 (q0 , a, a) = {(q0 , aa), (q1 , ε)} δ1 (q0 , b, b) = {(q0 , bb), (q1 , ε)} δ1 (q1 , a, a) = {(q1 , ε)} δ1 (q1 , b, b) = {(q1 , ε)} δ1 (q1 , ε, Z0 ) = {(q2 , ε)}

Konecˇny´ automat pro jazyk a∗ je velmi jednoduchy´: A2 = ({r} {a}, δ2 , r, {r}), kde δ2 (r, a) = r Vytvorˇ´ıme A = (Q, {a, b}, {Z0 , a, b}, δ, [q0 , r], Z0 , F ). δ([q0 , r], a, Z0 ) = {[q0 , r], aZ0 ])} δ([q0 , r], a, a) = {([q0 , r], aa), ([q1 , r], ε)} δ([q1 , r], a, a) = {[q1 , r], ε)} δ([q1 , r], ε, Z0 ) = {([q2 , r], ε)}

Jesˇteˇ doplnı´me: Q = {[q0 , r], [q1 , r], [q2 , r]} F = {[q2 , r]}

Jak vidı´me, je jazyk L17 pru˚nikem bezkontextove´ho a regula´rnı´ho jazyka, proto (i bez konstrukce automatu rozpozna´vajıćı´ho tento jazyk) mu˚zˇeme rˇ´ıci, zˇe je to bezkontextovy´ jazyk.


37

Prˇı´klad 2.7 Pomocı n´ uza´veˇrovyćh vlastnostı´ doka´zˇeme, o zˇe nenı´ bezkontextovy´ jazyk ∗ L18 = w ∈ {a, b, c} |w|a = |w|b = |w|c (stejny´ pocˇet a, b a c) Prˇedpokla´dejme, zˇe jazyk L18 je bezkontextovy´. Pak by pru˚nikem tohoto jazyka s jaky´mkoliv regula´rnı´m jazykem byl take´ bezkontextovy´ jazyk. Vezmeme regula´rnı´ jazyk R = a∗ b∗ c∗ . Jejich pru˚nikem je

L18 ∩ R = L2 = {an bn cn | n ≥ 0} O tomto jazyce vsˇak vı´me, zˇe nenı´ bezkontextovy´, proto L18 ∈ / L (CF ).

2.5

Deterministicke´ bezkontextove´ jazyky

2.5.1 Deterministicky´ za´sobnı´kovy´ automat Definice 2.5 (Deterministicky´ ZA) Za´sobnı´kovy´ automat A = (Q, Σ, Γ, δ, q0 , Z0 , F ) je deterministicky´, jestlizˇe pro kazˇde´ q ∈ Q, Z ∈ Γ platı´ za´rovenˇ

✍

• δ(q, a, Z) ma´ nejvy´sˇe jeden prvek pro kazˇde´ a ∈ Σ ∪ {ε}. • je-li δ(q, ε, Z) 6= ∅, pak δ(q, a, X) = ∅ ∀a ∈ Σ. To znamena´, zˇe v deterministicke´m za´sobnı´kove´m automatu ma´me v kazˇde´m kroku pra´veˇ jednu mozˇnost, jak reagovat (i vcˇetneˇ rozhodovańı´, zda ma´me cˇ´ıst ze vstupnı´ pa´sky). Definice 2.6 (Deterministicky´ bezkontextovy´ jazyk) Jazyk L se nazy´va´ deterministicky´ bezkontextovy´ jazyk, jestlizˇe existuje deterministicky´ za´sobnı´kovy´ automat (DZA) AD takovy´, zˇe L(AD ) = L.

✍

Z definice vyply´va´, zˇe pro kazˇde´ slovo patrˇ´ıcı´ do jazyka existuje pra´veˇ jeden vy´pocˇet v AD . Deterministicke´ bezkontextove´ jazyky budeme znacˇit DCF a trˇ´ıdu jazyku˚, ktere´ generujı´, L (DCF ). Veˇta 2.9 Trˇ´ıda jazyk§ generovanyćh deterministicky´mi za´sobnı´kovy´mi automaty je vlastnı´ podmnozˇinou trˇ´ıdy bezkontextovyćh jazyku˚: L (DCF ) ⊂ L (CF )

(2.8)

✎


38

Du˚kaz: To, zˇe platı´ L (DCF ) ⊆ L (CF ), je zrˇejme´ – vyply´va´ to z toho, zˇe deterministicky´ za´sobnı´kovy´ automat je vlastneˇ specia´lnı´m prˇ´ıpadem (obecne´ho) za´sobnı´kove´ho automatu, a vı´me (viz du˚sledek 2.7), zˇe trˇ´ıda jazyku˚ generovanyćh bezkontextovy´mi jazyky je ekvivalentnı´ trˇ´ıdeˇ jazyku˚ rozpozna´vanyćh za´sobnı´kovy´mi automaty. Vlastnı´ inkluzi (tj. podmnozˇinu, L (DZA) ( L (CF )) lze doka´zat tak, zˇe najdeme jazyk patrˇ´ıcı´ do druhe´, ale nepatrˇ´ıcı´ do prvnı´ trˇ´ıdy. Bezkontextovy´m jazykem, ktery´ nenı´ deterministicky´m bezkontextovy´m, je naprˇ´ıklad L16 = wwR | w ∈ {a, b}∗ (za´sobnı´kovy´ automat pro tento jazyk je v prˇ´ıkladu 2.6 na straneˇ 36).

"

Tento jazyk je velmi podobny´ jazyku L14 , ale slova nejsou v polovineˇ rozdeˇlena znakem c. Za´sobnı´kovy´ automat pro tento jazyk je mozˇne´ sestrojit podobneˇ jako pro jazyk L14 v prˇ´ıkladu 2.1 na straneˇ 24, ale bude to rozhodneˇ automat nedeterministicky´ – nevı´me, ve ktere´m okamzˇiku vlastneˇ prˇecha´zı´me do druhe´ poloviny rozpozna´vane´ho slova (nema´me mozˇnost si prˇedem tuto informaci zjistit a obeˇ poloviny slova majı´ podobnou strukturu), a proto v kazˇde´m kroku prˇi nacˇ´ıtańı´ prvnı´ poloviny slova potrˇebujeme mozˇnost nedeterministicky zvolit bud’ pokracˇovańı´ v prvnı´ polovineˇ slova, a nebo prˇechod do druhe´. 2

2.5.2 Uza´veˇrove´ vlastnosti deterministickyćh bezkontextovyćh jazyku˚ Veˇta 2.10 Trˇ´ıda jazyku˚ L (DCF ) je uzavrˇena vzhledem k operaci pru˚niku s regula´rnı´m jazykem.

✎

Du˚kaz: Du˚kaz je stejny´ jako u (obecneˇ) bezkontextovyćh jazyku˚, viz veˇta 2.8 na straneˇ 35. 2

"

Veˇta 2.11 Trˇ´ıda jazyku˚ L (DCF ) nenı´ uzavrˇena vzhledem k operaci pru˚niku. Du˚kaz: Du˚kaz je stejny´ jako u (obecneˇ) bezkontextovyćh jazyku˚, viz veˇta 1.13 na straneˇ 18. 2 Da´le budeme potrˇebovat tuto pomocnou veˇtu (lemma):

✎ "


39

Lemma 2.12 Ke kazˇde´mu DZA A lze zkonstruovat DZA A0 , ktery´ kazˇdy´ vstup docˇte do konce.

✎

Du˚kaz je slozˇity´, je trˇeba vyrˇesˇit proble´m zacyklenı´ v epsilonovyćh krocıćh (praće se za´sobnı´kem). Veˇta 2.13 Trˇ´ıda jazyku˚ L (DCF ) je uzavrˇena vzhledem k operaci doplnˇku.

✎

Du˚kaz: Kazˇdy´ deterministicky´ za´sobnı´kovy´ automat, ktery´ vstup docˇte do konce, doka´zˇe v konecˇne´m pocˇtu kroku˚ rozhodnout, zda slovo patrˇ´ı nebo nepatrˇ´ı do jazyka rozpozna´vane´ho tı´mto automatem (lemma 2.12). Proto je postup na´sledujıćı´:

"

• sestrojı´me k pu˚vodnı´mu automatu A za´sobnı´kovy´ automat A0 , ktery´ cˇte kazˇdy´ vstup azˇ do konce, • zameˇnı´me koncove´ a nekoncove´ stavy. 2 Veˇta 2.14 Trˇ´ıda jazyku˚ L (DCF ) nenı´ uzavrˇena vzhledem k operaci sjednocenı´.

✎

Du˚kaz: Vyply´va´ z De Morganovyćh za´konu˚: L1 ∩ L2 = L1 ∪ L2

(2.9)

"

Prˇedpokla´dejme, zˇe trˇ´ıda jazyku˚ L (DCF ) je uzavrˇena vzhledem k operaci sjednocenı´. Pak by na prave´ straneˇ vztahu (2.9) byla mnozˇina deterministickyćh bezkontextovyćh jazyku˚, jenzˇe v mnozˇineˇ na prave´ straneˇ rovnosti se mohou vyskytovat i jazyky, ktere´ nejsou deterministicke´ bezkontextove´ (tato trˇ´ıda jazyku˚ nenı´ uzavrˇena vzhledem k operaci pru˚niku). Proto trˇ´ıda jazyku˚ L (DCF ) nemu˚zˇe by´t uzavrˇena vzhledem k operaci sjednocenı´. 2 Du˚sledek 2.15 L (DCF ) ⊂ L (CF )

(2.10)

➠

Kapitola

3

Jazyky typu 0 V te´to kapitole se budeme zaby´vat nejvysˇsˇ´ı trˇ´ıdou jazyku˚ Chomske´ho hierarchie s (te´meˇrˇ) obecny´m tvarem pravidel, jazyky typu 0. Strucˇneˇ se podı´va´me na gramatiky typu 0 a pak se budeme veˇnovat prˇedevsˇ´ım za´kladnı´ varianteˇ Turingova stroje.

3.1

Gramatiky typu 0

Definice 3.1 (Gramatika typu 0) Gramatika typu 0 je takova´ gramatika, jejı´zˇ pravidla jsou ve tvaru α → β, α ∈ (N ∪ T )∗ N (N ∪ T )∗ , β ∈ (N ∪ T )∗

✍

Definice 3.2 (Kurodova norma´lnı´ forma pro gramatiky typu 0) Gramatika typu 0 je v KNF, jestlizˇe pro vsˇechna jejı´ pravidla α → β platı´ |α| ≤ 2, |β| ≤ 2.

✍

Veˇta 3.1 Ke kazˇde´ gramatice G typu 0 lze sestrojit ekvivalentnı´ gramatiku G0 v KNF.

✎

Du˚kaz: • pravidla v bezkontextove´m tvaru: pouzˇijeme algoritmus pro prˇevod na Chomske´ho NF. • pravidla, ktera´ nejsou bezkontextove´ho typu: upravı´me pravidla podle na´sledujıćı´ho algoritmu. Vstup: gramatika bez jednoduchyćh pravidel typu X → Y,

40

X, Y ∈ N

"

KAPITOLA 3 JAZYKY TYPU 0

41

1. Pro vsˇechna pravidla: • Vsˇechny termina´ly (na leve´ i prave´ straneˇ pravidla) a ∈ T nahradı´me „pomocny´mi“ netermina´ly Na . • Pro vsˇechny netermina´ly vytvorˇene´ v prˇedchozı´m bodu prˇida´me pravidlo Na → a. 2. Pravidla A → B1 B2 . . . Bn , n > 2 nahradı´me pravidly A → B1 X1 X1 → B2 X2 .. . Xn−2 → Bn−1 Bn 3. Pravidla A1 A2 . . . Am → B1 B2 . . . Bm , m > 2 nahradı´me pravidly A1 A2 → B1 X1 X1 A3 → B2 X2 .. . Xm−2 Am → Bm−1 Bm

4. Nezkracujıćı´ pravidla A1 A2 . . . Am → B1 B2 . . . Bn , 2 < m ≤ n nahradı´me pravidly A1 A2 → B1 X1 X1 A3 → B2 X2 .. . Xm−2 Am → Bm−1 Xm−1

Xm−1 → Bm Xm Xm → Bm+1 Xm+1 .. . Xn−2 → Bn−1 Bn

5. Zkracujıćı´ pravidla A1 A2 . . . Am → B1 B2 . . . Bn , n < m nahradı´me pravidly A1 A2 → B1 X1 X1 A3 → B2 X2 .. . Xn−1 An+1 → Bn Xn

Xn An+2 → Xn+1 .. . Xm−3 Am−1 → Xm−2 Xm−2 Am → ε 2


42

Prˇı´klad 3.1 Postup si uka´zˇeme na gramatice 1 S → AaBC

2 3

, C → cBAa | bS 4

AaBc → d 5

BA → abcd

Provedeme na´hradu termina´lu˚ a ∈ T novy´mi netermina´ly Na . Ty´ka´ se to pra4 a . 5 Pravidlo 3 nemusı´me da´le zpracova´vat, uzˇ odpovı´da´ Kurodoveˇ NF, videl po nahrazenı´ termina´lu˚ je C → Nb S. 1 a . 2 Nejdrˇ´ıv zpracujeme pravidla bezkontextove´ho typu S → AX1 X1 → Na X2 X2 → BC

C → Nc X3 X3 → BX4 X4 → ANa

3 a 4 – jedno je zkracujıćı´ a druhe´ nezkracujıćı´: Zby´vajı´ pravidla

BA → Na X5 Na X5 → Nb X6 X6 → Nc Nd

ANa → Nd X7 X7 B → X8 X8 Nc → ε

Cela´ gramatika po prˇevodu do KNF: S → AX1 X1 → Na X2 X2 → BC C → Nc X3

3.2

X3 → BX4 X4 → ANa BA → Na X5 Na X5 → Nb X6

X6 → Nc Nd ANa → Nd X7 X7 B → X8 X8 Nc → ε

Na → a Nb → b Nc → c Nd → d

Stroje rozpozna´vajıćı´ jazyky typu 0

Existujı´ dva typy stroju˚ (resp. matematickyćh modelu˚), ktere´ rozpozna´vajı´ jazyky typu 0 – za´sobnı´kovy´ automat rozsˇ´ırˇeny´ o dalsˇ´ı za´sobnı´k a Turingu˚v stroj.

3.2.1 Za´sobnı´kovy´ automat se dveˇma za´sobnı´ky Obecneˇ mu˚zˇeme mı´t jaky´koliv pocˇet za´sobnı´ku˚, ale da´ se doka´zat, zˇe k rozpozna´vańı´ jazyku˚ typu 0 stacˇ´ı dva za´sobnı´ky, resp. zˇe ke kazˇde´mu za´sobnı´kove´mu


43

automatu s jaky´mkoliv pocˇtem za´sobnı´ku˚ je mozˇno vytvorˇit ekvivalentnı´ (rozpozna´vajıćı´ stejny´ jazyk) se dveˇma za´sobnı´ky. Definice 3.3 (Za´sobnı´kovy´ automat se dveˇma za´sobnı´ky) Za´sobnı´kovy´ automat se dveˇma za´sobnı´ky je A2 = (Q, Σ, Γ1 , Γ2 , δ, q0 , Z1 , Z2 , F ), kde

✍

• Z1 ∈ Γ1 je pocˇa´tecˇnı´ za´sobnı´kovy´ symbol prvnı´ho za´sobnı´ku, abecedou prvnı´ho za´sobnı´ku je Γ1 , • Z2 ∈ Γ2 je pocˇa´tecˇnı´ za´sobnı´kovy´ symbol druhe´ho za´sobnı´ku, abecedou druhe´ho za´sobnı´ku je Γ2 , • δ funkce je definovańa takto: δ : Q × (Σ ∪ {ε}) × Γ1 × Γ2 → Q × Γ∗1 × Γ∗2 δ(q1 , a, b1 , b2 ) ∈ (q2 , γ1 , γ2 ), a ∈ Σ ∪ {ε}, b1 ∈ Γ1 , b2 ∈ Γ2 , γ1 ∈ Γ∗1 , γ2 ∈ Γ∗2 • vsˇe ostatnı´ se prˇejı´ma´ z definice za´sobnı´kove´ho automatu (s jednı´m za´sobnı´kem). Definice 3.4 (Konfigurace a prˇechod mezi konfiguracemi) Konfigurace za´sobnı´kove´ho automatu se dveˇma za´sobnı´ky je

✍

(q, w, γ1 , γ2 ) ∈ Q × Σ∗ × Γ∗1 × Γ∗2 (stav, neprˇecˇtena´ cˇa´st vstupu, obsah prvnı´ho za´sobnı´ku, obsah druhe´ho za´sobnı´ku). Prˇechod mezi konfiguracemi za´sobnı´kove´ho automatu se dveˇma za´sobnı´ky je relace (qi , aα, b1 γ1 , b2 γ2 ) ` (qj , β1 γ1 , β2 γ2 )

⇐⇒

δ(qi , a, b1 , b2 ) 3 (qj , β1 , β2 )

Podobneˇ jako u za´sobnı´kovyćh automatu˚ s jednı´m za´sobnı´kem bychom mohli definovat take´ reflexivnı´ a tranzitivnı´ uza´veˇr relace a take´ jazyk rozpozna´vany´ automatem, to necha´va´me na cˇtena´rˇi, definice budou prakticky stejne´. Prˇı´klad 3.2 Vytvorˇ´ıme za´sobnı´kovy´ automat se dveˇma za´sobnı´ky pro jazyk, o ktere´m vı´me, zˇe nenı´ bezkontextovy´: L2 = {an bn cn | n ≥ 0} A2 = ({q0 , q1 , q2 }, {a, b, c}, {a, Z1 }, {b, Z2 }, δ, Z1 , Z2 , ∅) δ funkce pracuje takto: • v prvnı´ fa´zi (stav q0 ) nacˇ´ıta´me symboly a a ukla´da´me je do prvnı´ho za´sobnı´ku, druhy´ za´sobnı´k zatı´m nenı´ pouzˇ´ıvań,


44

• v druhe´ fa´zi (stav q1 ) nacˇ´ıta´me symboly b, prˇitom vyjı´ma´me z prvnı´ho za´sobnı´ku symboly a (tak je zajisˇteˇn stejny´ pocˇet a a b) a za´rovenˇ ukla´da´me symboly b do druhe´ho za´sobnı´ku, • v trˇetı´ fa´zi (stav q2 ) musı´ jizˇ by´t prvnı´ za´sobnı´k pra´zdny´, nacˇ´ıta´me ze vstupu symboly c a za´rovenˇ vyjı´ma´me z druhe´ho za´sobnı´ku symboly b (tak je zajisˇteˇn stejny´ pocˇet b a c). δ(q0 , δ(q0 , δ(q0 , δ(q1 ,

a, a, b, b,

Z1 , a, a, a,

Z2 ) Z2 ) Z2 ) b)

= = = =

(q0 , (q0 , (q1 , (q1 ,

aZ1 , aa, ε, ε,

Z2 ) Z2 ) bZ2 ) bb)

δ(q1 , δ(q2 , δ(q0 , δ(q2 ,

c, c, ε, ε,

Z1 , Z1 , Z1 , Z1 ,

b) b) Z2 ) Z2 )

= = = =

(q2 , (q2 , (q0 , (q2 ,

Z1 , Z1 , ε, ε,

ε) ε) ε) ε)

Uka´zka rozpoznańı´ slova aabbcc: (q0 , aabbcc, Z1 , Z2 ) ` (q0 , abbcc, aZ1 , Z2 ) ` (q0 , bbcc, aaZ1 , Z2 ) ` (q1 , bcc, aZ1 , bZ2 ) ` ` (q1 , cc, Z1 , bbZ2 ) ` (q2 , c, Z1 , bZ2 ) ` (q2 , ε, Z1 , Z2 ) ` (q2 , ε, ε, ε)

3.2.2 Turingu˚v stroj Cˇinnost Turingova stroje jsme si jizˇ trochu osveˇtlili v kurzu Teorie jazyku˚ a automatu˚ I. Shrneme si za´kladnı´ vlastnosti: • konecˇna´ (konecˇneˇstavova´) rˇ´ıdicı´ jednotka, • nekonecˇna´ pa´ska (obvykle doprava nekonecˇna´), • cˇtecı´ a za´pisova´ hlava mu˚zˇe cˇ´ıst symbol z pa´sky, prˇepsat ho jiny´m symbolem, pohybuje se o 1 polıćˇko doleva nebo doprava, • vy´pocˇet koncˇ´ı prˇi prˇechodu do neˇktere´ho koncove´ho stavu, nemusı´ by´t prˇecˇtena´ cela´ pa´ska. Definice 3.5 (Turingu˚v stroj) Turingu˚v stroj je usporˇa´dana´ sˇestice M = (Q, Σ, Γ, δ, q0 , F ), kde • Q je konecˇna´ nepra´zdna´ mnozˇina stavu˚, • Σ je konecˇna´ nepra´zdna´ vstupnı´ abeceda (symboly, ze kteryćh se mu˚zˇe skla´dat vstupnı´ slovo), Σ ⊆ Γ,

✍


45

• Γ je konecˇna´ nepra´zdna´ pa´skova´ abeceda (symboly, ktere´ se mohou vyskytovat na pa´sce), • q0 ∈ Q je pocˇa´tecˇnı´ stav, • F ⊆ Q je mnozˇina koncovyćh stavu˚, • δ je prˇechodova´ funkce: δ : Q × Γ → Q × Γ × {−1, 0, 1}, jinak δ(qi , a) → (qj , b, P ), qi , qj ∈ Q, a, b ∈ Γ, P ∈ {−1, 0, 1} Podle definice δ funkce mu˚zˇeme odvodit cˇinnost Turingova stroje – v kazˇde´m kroku, kdy je pouzˇito δ(qi , a) → (qj , b, P ), qi , qj ∈ Q, a, b ∈ Γ, P ∈ {−1, 0, 1}, jsou provedeny na´sledujıćı´ akce: • jsme ve stavu qi a na pa´sce cˇtecı´ a za´pisova´ hlava pra´veˇ ukazuje na polıćˇko oznacˇene´ a, • prˇejdeme do stavu qj , • symbol a na pa´sce prˇepı´sˇeme symbolem b, • posuneme cˇtecı´ a za´pisovou hlavu podle prˇedpisu P . Takto definovany´ Turingu˚v stroj je deterministicky´. Pra´zdna´ polıćˇka pa´sky se obvykle oznacˇujı´ symbolem t (nebo pı´smenem B, Blank), slovo je od pra´zdnyćh polıćˇek oddeˇleno (tedy obklopeno) symboly $, tyto symboly v prˇechodove´ funkci poma´hajı´ zjistit, zda jsme na zacˇa´tku cˇi konci slova. Je mozˇne´ stanovit take´ dva ru˚zne´ symboly – jeden pro vymezenı´ zacˇa´tku a druhy´ pro vymezenı´ konce slova (naprˇ´ıklad $ a #). Hranicˇnı´ symbol (-y) je take´ soucˇa´stı´ pa´skove´ abecedy. Mnozˇina F koncovyćh stavu˚ by´va´ cˇasto tvorˇena dveˇma stavy, jednı´m pro prˇijetı´ a jednı´m pro odmı´tnutı´ slova: F = {qaccept , qreject }, prˇ´ıpadneˇ mı´sto qreject je neˇkdy pouzˇito qerror . Definice 3.6 (Konfigurace Turingova stroje) Konfigurace Turingova stroje M, kde M = (Q, Σ, Γ, δ, q0 , F ), je (w1 , q, w2 ), kde w1 ∈ Γ je cˇa´st pa´sky prˇed cˇtecı´ a za´pisovou hlavou, q ∈ Q je stav, ve ktere´m se rˇ´ıdicı´ jednotka nacha´zı´ a w2 ∈ Γ je cˇa´st pa´sky za cˇtecı´ a za´pisovou hlavou, cˇtecı´ a za´pisova´ hlava ukazuje na prvnı´ symbol rˇeteˇzce w2 . Pocˇa´tecˇnı´ konfigurace je (ε, q0 , w0 ) nebo ($, q0 , w0 $) (pokud chceme zahrnout do konfigurace i hranicˇnı´ symboly), w0 ∈ Σ je vstupnı´ slovo, ktere´ ma´ by´t zpracovańo. Koncova´ konfigurace je (w1 , qf , w2 ) (resp. ($w1 , qf , w2 $)), qf ∈ F, w1 , w2 ∈ Γ∗ .

✍


46

Prˇı´klad 3.3 Naprˇ´ıklad konfigurace (abbca, q, daab) znamena´, zˇe se stroj nacha´zı´ ve stavu q, na pa´sce je slovo abbcadaab a cˇtecı´ a za´pisova´ hlava ukazuje na sˇesty´ symbol slova – d.

Definice 3.7 (Relace prˇechodu mezi konfiguracemi) Relace prˇechodu mezi konfiguracemi je urcˇena takto:

✍

(α, qi , aβ) ` (αb, qj , β) ⇔ δ(qi , a) = (qj , b, 1)

(3.1)

(α, qi , aβ) ` (α, qj , bβ) ⇔ δ(qi , a) = (qj , b, 0)

(3.2)

(αc, qi , aβ) ` (α, qj , cbβ) ⇔ δ(qi , a) = (qj , b, −1)

(3.3)

V prvnı´m prˇ´ıpadeˇ se cˇtecı´ a za´pisova´ hlava posunuje doprava, v druhe´m zu˚sta´va´ na mı´steˇ (tj. v dalsˇ´ım kroku bude cˇ´ıst tote´zˇ polıćˇko jako v tomto) a v trˇetı´m prˇ´ıpadeˇ se posunuje doleva. Prˇı´klad 3.4 Sestrojı´me Turingu˚v stroj rozpozna´vajıćı´ jazyk L2 = {an bn cn | n ≥ 0} M = ({q0 , qP , qA , qB , qC , qf , qaccept }, {a, b, c}, {a, a ¯, b, ¯b, c, c¯, t, $}, δ, {qaccept }) Budeme postupovat takto: oznacˇ´ıme prvnı´ a (tj. prˇepı´sˇeme symbolem a ¯), najdeme prvnı´ b, oznacˇ´ıme ho, pak najdeme prvnı´ c, takte´zˇ oznacˇ´ıme, potom prˇejdeme na zacˇa´tek (postupujeme doleva, dokud nenajdeme nejblizˇsˇ´ı oznacˇene´ a ¯), posuneme se o polıćˇko da´le na prvnı´ neoznacˇene´ a, oznacˇ´ıme ho, atd. Jednotlive´ stavy znamenajı´: • qA – oznacˇili jsme a, prˇeskakujeme symboly a, ¯b, hleda´me prvnı´ neoznacˇene´ b, • qB – oznacˇili jsme b, prˇeskakujeme symboly b, c¯, hleda´me prvnı´ neoznacˇene´ c, • qC – oznacˇili jsme c, vracı´me se na zacˇa´tek k poslednı´mu oznacˇene´mu a ¯, prˇi pohybu doleva prˇeskakujeme vsˇechny symboly c¯, b, ¯b, a. Definujeme δ funkci: δ(q0 , $) = (qaccept , 0) (prˇijali jsme pra´zdne´ slovo) δ(q0 , a) = (qA , a ¯, 1) δ(qB , b) = (qB , b, 1) δ(qP , a) = (qA , a ¯, 1) δ(qB , c¯) = (qB , c¯, 1) δ(qA , a) = (qA , a, 1) δ(qB , c) = (qC , c¯, −1) δ(qA , ¯b) = (qA , ¯b, 1) δ(qC , X) = (qC , X, −1), δ(qA , b) = (qB , ¯b, 1) X ∈ {a, b, ¯b, c¯}

δ(qC , a ¯) = (qP , a ¯, 1) δ(q0 , ¯b) = (qf , ¯b, 1) δ(qf , ¯b) = (qf , ¯b, 1) δ(qf , c¯) = (qf , c¯, 1) δ(qf , $) = (qaccept , $, 0)


47

Uka´zka zpracovańı´ slova abc: (ε, q0 , abc) ` (¯ a, qA , bc) ` (¯ a¯b, qB , c) ` (¯ a, qC , ¯b¯ c) ` (ε, qC , a ¯¯b¯ c) ` (¯ a, q0 , ¯b¯ c) ` ¯ ¯ ¯ ` (¯ ab, qf , c¯) ` (¯ ab¯ c, qf , ε) ` (¯ ab¯ c, qaccept , ε) Jestlizˇe zaznamena´me i hranicˇnı´ symboly, zpracovańı´ bude vypadat takto: ($, q0 , abc$) ` ($¯ a, qA , bc$) ` ($¯ a¯b, qB , c$) ` ($¯ a, qC , ¯b¯ c$) ` ($, qC , a ¯¯b¯ c$) ` ¯ ¯ ¯ ¯ ` ($¯ a, q0 , b¯ c$) ` ($¯ ab, qf , c¯$) ` ($¯ ab¯ c, qf , $) ` ($¯ ab¯ c, qaccept , $) Uka´zka zpracovańı´ slova aabbcc: (ε, q0 , aabbcc) ` (¯ a, qA , abbcc) ` (¯ aa, qA , bbcc) ` (¯ aa¯b, qB , bcc) ` (¯ aa¯bb, qB , cc) ` ` (¯ aa¯b, qC , b¯ cc) ` (¯ aa, qC , ¯bb¯ cc) ` (¯ a, qC , a¯bb¯ cc) ` (ε, qC , a ¯a¯bb¯ cc) ` (¯ a, q0 , a¯bb¯ cc) ` ¯ ¯ ¯ ¯ ¯ ¯ ¯ ¯ ` (¯ aa ¯, qA , bb¯ cc) ` (¯ aa ¯b, qA , b¯ cc) ` (¯ aa ¯bb, qB , c¯c) ` (¯ aa ¯bb¯ c, qB , c) ` (¯ aa ¯bb, qC , c¯c¯) ` ` (¯ aa ¯¯b, qC , ¯b¯ cc¯) ` (¯ aa ¯, qC , ¯b¯b¯ cc¯) ` (¯ a, qC , a ¯¯b¯b¯ cc¯) ` (¯ aa ¯, q0 , ¯b¯b¯ cc¯) ` (¯ aa ¯¯b, qf , ¯b¯ cc¯) ` ¯ ¯ ¯ ¯ ¯ ¯ ¯ ¯ ` (¯ aa ¯bb, qf , c¯c¯) ` (¯ aa ¯bb¯ c, qf , c¯) ` (¯ aa ¯bb¯ cc¯, qf , ε) ` (¯ aa ¯bb¯ cc¯, qaccept , ε) Uka´zka zpracovańı´ slova ac: (ε, q0 , ac) ` (¯ a, qA , c) chyba ⇒ slovo ac nenı´ prˇijato. Uka´zka zpracovańı´ slova ε: (ε, q0 , ε) ` (ε, qaccept , ε)

Pozna´mka: Vsˇimneˇme si rozdı´lu mezi cˇinnostı´ Turingova stroje a drˇ´ıve definovanyćh automatu˚: • Turingu˚v stroj nejen cˇte vstupnı´ pa´sku, mu˚zˇe ji i zapisovat, • cˇtecı´ a za´pisova´ hlava se mu˚zˇe (nemusı´) pohybovat ru˚zny´mi smeˇry, nejen doprava, • nepotrˇebujeme za´sobnı´k, ale prˇesto mu˚zˇeme uchova´vat i jinou informaci nezˇ oznacˇenı´ stavu, ve ktere´m pra´veˇ jsme – kamkoliv na pa´sku si mu˚zˇeme cokoliv poznamenat a pozdeˇji tuto informaci vyuzˇ´ıt, • na Turingoveˇ stroji lze prova´deˇt i vy´pocˇty. Turingovy´mi stroji se budeme podrobneˇji zaby´vat v navazujıćı´m kurzu Teorie vycˇ´ıslitelnosti.

❁


48

3.2.3 Varianty Turingova stroje ˇ ekli jsme si, zˇe Turingu˚v stroj je v za´kladnı´ definici deterministicky´. Proto varianty R mu˚zˇeme prˇedevsˇ´ım rozdeˇlit podle tohoto krite´ria: • deterministicky´ – za´kladnı´ varianta, • nedeterministicky´ – pro tenty´zˇ stav a obsah pa´sky lze definovat vıće ru˚znyćh akcı´. Podobneˇ, jako za´sobnı´kovy´ automat mu˚zˇe mı´t vıće za´sobnı´ku˚, Turingu˚v stroj mu˚zˇe mı´t vıće pa´sek: • jednopa´skovy´ – za´kladnı´ varianta, • vıćepa´skovy´ – ma´me vıće pa´sek, kazˇda´ ma´ vlastnı´ cˇtecı´ a za´pisovou hlavu, tyto hlavy se mohou pohybovat navza´jem neza´visle (naprˇ´ıklad prvnı´ doprava, druha´ doleva a trˇetı´ trˇeba zu˚stane na mı´steˇ v tomte´zˇ kroku zpracovańı´). Na jedne´ pa´sce mu˚zˇe by´t i vıće stop (podobneˇ jako na pameˇt’ovyćh me´diıćh, trˇeba za´lohovacıćh pa´skaćh): • jednostopy´ – na (kazˇde´) pa´sce je jen jedna stopa, • vıćestopy´ – na pa´sce mu˚zˇe by´t vıće stop, ale narozdı´l od vıćepa´skove´ho automatu zde vsˇechny stopy te´zˇe pa´sky majı´ spolecˇnou cˇtecı´ a za´pisovou hlavu. Da´le mu˚zˇeme stanovit mozˇnost pohybu cˇtecı´ a za´pisove´ hlavy: • mozˇnost pohybu {−1, 0, 1} – cˇtecı´ a za´pisova´ hlava se mu˚zˇe pohybovat doleva nebo doprava, a nebo zu˚stat na mı´steˇ, • mozˇnost pohybu {−1, 1} – cˇtecı´ a za´pisova´ hlava se musı´ pohybovat v kazˇde´m kroku, a to doleva nebo doprava, nesmı´ zu˚stat na mı´steˇ. Pa´ska mu˚zˇe by´t • jednostranneˇ nekonecˇna´ – vstupnı´ slovo je na zacˇa´tku vy´pocˇtu umı´steˇno na zacˇa´tek pa´sky, prˇed neˇ jizˇ nenı´ mozˇne´ nic napsat, • oboustranneˇ nekonecˇna´ – za´kladnı´ varianta. Lze doka´zat, zˇe vsˇechny vy´sˇe uvedene´ varianty jsou navza´jem ekvivalentnı´, vsˇechny varianty lze prˇeve´st na za´kladnı´ variantu – deterministicky´ jednopa´skovy´ jednostopy´ automat, jehozˇ cˇtecı´ a za´pisova´ hlava se mu˚zˇe pohybovat obeˇma smeˇry nebo zu˚stat na mı´steˇ a lze zapisovat i prˇed vstupnı´ slovo.


3.3

49

Vztah Turingovyćh stroju˚ k jazyku˚m typu 0

Zde uka´zˇeme, zˇe jazyky rozpozna´vane´ Turingovy´m strojem jsou pra´veˇ jazyky typu 0. Pro tuto vlastnost se take´ jazyku˚m typu 0 rˇ´ıka´ rekurzı´vneˇ spocˇetne´ jazyky, protozˇe Turingu˚v stroj vlastneˇ pracuje na principu rekurze. Definice 3.8 (Rekurzı´vneˇ spocˇetny´ jazyk) Jazyk nazveme rekurzı´vneˇ spocˇetny´ (rekurzı´vneˇ vycˇ´ıslitelny´, cˇa´stecˇneˇ rekurzivnı´), pokud je prˇijı´mań neˇjaky´m Turingovy´m strojem (tento Turingu˚v stroj se na slovo patrˇ´ıcı´ do jazyka zastavı´ v akceptujıćı´m stavu, na slovo nepatrˇ´ıcı´ do jazyka se bud’ zastavı´ v odmı´tajıćı´m stavu nebo se dostane do nekonecˇne´ smycˇky).

✍

Definice 3.9 (Rekurzı´vnı´ jazyk) Jazyk nazveme rekurzı´vnı´, pokud je rozhodovań neˇjaky´m Turingovy´m strojem (tento Turingu˚v stroj se pro jake´koliv slovo zastavı´, a to na slovo jazyka v akceptujıćı´m stavu a na slovo nepatrˇ´ıcı´ do jazyka v odmı´tajıćı´m stavu, pro zˇa´dny´ vstup neprˇejde do nekonecˇne´ smycˇky).

✍

Veˇta 3.2 Ke kazˇde´ gramatice G typu 0 lze sestroji Turingu˚v stroj M takovy´, zˇe platı´ L(M) = L(G).

✎

Du˚kaz: Podle gramatiky G = (N, T, P, S) sestrojı´me nedeterministicky´ dvoustopy´ Turingu˚v stroj M = (Q, Σ, Γ, δ, q0 , F ). Prvnı´ stopa obsahuje vstupnı´ slovo, nemeˇnı´ se, slouzˇ´ı pro kontrolu, druha´ stopa simuluje derivaci v gramatice, obsahuje veˇtnou formu, u ktere´ v derivaci pra´veˇ jsme (na zacˇa´tku to je S).

"

1. Nedeterministicky zvolı´me neˇktere´ pravidlo α → β v gramatice. 2. Pokud se α nacha´zı´ ve veˇtne´ formeˇ, zvolı´me neˇktery´ vy´skyt α a prˇepı´sˇeme ho na β; pokud |β| = 6 |α|, nejdrˇ´ıv vhodneˇ posuneme vsˇechny symboly za rˇeteˇzcem α doleva nebo doprava. 3. Porovna´me vstup na prvnı´ stopeˇ s obsahem druhe´ stopy – pokud je stejny´, vstup prˇijmeme, jinak zpeˇt k bodu 1. Da´le v du˚kazu nebudeme pokracˇovat, postup si uka´zˇeme na prˇ´ıkladu. Prˇı´klad 3.5 Vytvorˇ´ıme gramatiku typu 0 pro jazyk

2


50

L19 = L2 − {ε} = {an bn cn | 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 → Bb aB → aaAb Uka´zka odvozenı´: S ⇒ aAbX ⇒ abAX ⇒ abBXc ⇒ aBbXc ⇒ aaAbbXc ⇒ aabAbXc ⇒ aabbAXc ⇒ ⇒ aabbcc Podle te´to gramatiky sestrojı´me Turingu˚v stroj. Vy´znam jednotlivyćh stavu˚: • q0 . . . nedeterministicky vybereme pravidlo, • q1 , q2 , . . . , q6 . . . vybrali jsme 1., 2., . . . , 6. pravidlo, ted’ nedeterministicky vybereme, kde ho chceme pouzˇ´ıt, • q11 . . . uzˇ jsme si vybrali mı´sto pro uplatneˇnı´ prvnı´ho pravidla, zpracovali jsme prvnı´ symbol pravidla (prvnı´ znak α prˇepı´sˇeme na prvnı´ znak β), • q12 . . . prˇepisujeme druhy´ symbol pravidla . . . .. . • q21 . . . uzˇ jsme si vybrali mı´sto pro uplatneˇnı´ druhe´ho pravidla, zpracovali jsme prvnı´ symbol pravidla .. . • qZ . . . prˇepsali jsme cele´ pravidlo, vracı´me se na zacˇa´tek veˇtne´ formy, bude dalsˇ´ı pravidlo, • qK . . . kontrola, jestli ma´me skoncˇit, • qJN . . . jesˇteˇ ne (jesˇteˇ neskoncˇit, stopy majı´ ru˚zny´ obsah). Postup si nejdrˇ´ıv uka´zˇeme na pru˚beˇhu vy´pocˇtu slova, ktere´ bylo v gramatice pro uka´zku odvozeno. Na pru˚beˇhu vy´pocˇtu vidı´me, zˇe hornı´ stopa se nemeˇnı´, zatı´mco na dolnı´ probı´ha´ simulace generovańı´ tohoto slova v gramatice. ! ! a a b b c c $ a a b b c c $ $ $ , q1 , , q0 , ` ` S $ t t t t t S $ t t t t t $ $


51

`

a b b c c $ $ a , q11 , $ t t t t t $ a

!

`

$ a a b b c c $ , q13 , $ a A b t t t t

!

`

`

b c c $ $ a a b , qZ , X $ t t $ a A b

!

`

`

$ a a b b c c $ , qZ , $ a A b X $ t t

!

`

`

$ a a b b c c $ , qK , $ a A b X $ t t

!

`

b b c c $ $ a a , q12 , t t t t t $ a A

!

`

! $ a a b b c c $ , q14 , ` $ a A b X t t t ! b b c c $ $ a a , qZ , ` b X $ t t $ a A ! $ a a b b c c $ , qZ , ` $ a A b X $ t t

` ... `

$ a a b b c c $ , q0 , $ a A b X $ t t

!

` ...

Definujeme δ funkci – pro kazˇde´ U ∈ Σ ∪ {t}, V ∈ Γ: Nedeterministicky vybereme pravidlo gramatiky, ktere´ budeme uplatnˇovat na obsah druhe´ stopy: !) ! ! ! ! ( U U U U U = q1 , , 0 , q2 , , 0 , q3 , , 0 , . . . , q6 , , 0 δ q0 , V V V V V Zpracovańı´ prvnı´ho pravidla – nejdrˇ´ıv nedeterministicky vybereme, na ktere´m mı´steˇ rˇeteˇzce pravidlo uplatnı´me, a pak pro α → β zacˇneme prˇepisovat α na β: ! ( ! !) U U U = q1 , , 1 , q11 , , 1 δ q1 , S a S ! ! U U δ q1 , , 1 , M 6= S = q1 , M M ! ! ! ! U U U U δ q12 , δ q11 , = q13 , , 1 = q12 , , 1 V V b A ! ! ! ! U U U U δ q13 , = q14 , ,1 δ q14 , = qZ , , −1 V X V $ ! ! U U δ qZ , = qZ , , −1 , V 6= $ (jdeme na zacˇa´tek veˇtne´ formy) V V $ δ qZ , $

!

=

! $ qK , , 1 (jsme na zacˇa´tku) $


52

! U = qK , , 1 (kontrolujeme, jestli uzˇ jsme na konci odvozenı´ slova) U ! ! (obeˇ stopy majı´ stejny´ obsah ⇒ konec odvozenı´, konec $ $ δ qK , = qacc , , 0 praće) $ $ U δ qK , U

!

U δ qK , V

!

δ

δ

δ

δ

=

! (jesˇteˇ nenı´ konec, prˇejdeme na zacˇa´tek U qJN , , −1 , V 6= U pa´sky a zvolı´me dalsˇ´ı pravidlo) V

! ! ! ! $ $ U U δ qJN , = q0 , , 1 = qJN , , −1 qJN , $ $ V V ! ( ! !) U U U = q2 , , 1 , q21 , , 1 q2 , (zpracova´va´me druhe´ pravidlo) A b A ! ! U U , 1 , M 6= A = q2 , q2 , M M ! ! U U q21 , = qZ , , −1 b A

Trˇetı´ pravidlo je typu |α| < |β|, vsˇe za α posuneme doprava, aby se β vesˇla: ! ( ! !) (symbol 3 je zara´zˇka, abychom po poU U U δ q3 , = q3 , , 1 , qP , , 1 souvańı´ veˇdeˇli, kde ma´me zacˇ´ıt psa´t A A 3 rˇeteˇzec β) ! ! U U δ q3 , = q3 , , 1 , M 6= A M M Funkce pro posun na´sledujıćı´ho rˇeteˇzce o 1 polıćˇko doprava: ! ! U U δ qP , = qP , , 1 , V 6= $ (nejdrˇ´ıv se prˇesuneme na konec rˇeteˇzce) V V ! ! U U δ qP , = qP $ , , 1 $ $ ! ! U U = qP Z , , −1 , M ∈ {a, b, c, S, A, B, X, $} δ qP M , M V

KAPITOLA 3 JAZYKY TYPU 0 53 ! ! (zapamatujeme si M , prˇedchozı´ cˇa´stı´ δ fce ho pak U U ,1 = qP M , δ qP Z , zkopı´rujeme vpravo) M M ! ! (zara´zˇka 3 znamena´, zˇe jsme prˇi uplatnˇovańı´ 3. praU U δ qP Z , = q31 , , 1 vidla gramatiky posunuli vsˇe za tı´mto mı´stem o 1 3 B polıćˇko doprava, ted’ mu˚zˇeme zapsat pravou stranu pravidla, uzˇ se vejde) ! ! ! ! U U U U δ q31 , = q32 , ,1 δ q32 , = qZ , , −1 V X V c ! ! (6. pravidlo gramatiky vyzˇaduje posun o 2 polıćˇka, U U = qP , 0 , 1 δ qP Z , tedy musı´me funkci pro posun volat 2x) 6 6 ! ! ! ! U U U U = q62 , , 1 δ q61 , δ qP Z , 0 = q61 , , 1 a a B 6 ! ! ! ! U U U U = qZ , , −1 = q63 , , 1 δ q63 , δ q62 , b A V V Cˇtvrte´ pravidlo gramatiky vyzˇaduje posun na´sledujıćıćh symbolu˚ doleva (β je kratsˇ´ı nezˇ α): ! ! U U δ q4 , = q41 , , 1 A 4 ! ! U U = qR , , 1 (kontrolujeme, zda je ve sloveˇ prˇ´ıtomna cela´ α) δ q41 , X X Funkce pro posun na´sledujıćı´ho rˇeteˇzce o 1 polıćˇko doleva: ! ! ! ! U U U U = qRD , , 1 = qRV , , 1 δ qRV , δ qR , V V M V ! ! ! ! U U U U = qRZ , , −1 = qR , , 1 δ qRD , δ qRD , t V $ V ! ! ! ! U U U U δ qRZ , = qRZ , , −1 δ qRZ , = qZ , , −1 V V 4 c Pokud by β byla delsˇ´ı nezˇ 1 znak, museli bychom pro zpracovańı´ cele´ho pravidla pouzˇ´ıt stavy q42 , q43 , . . . atd. pro dalsˇ´ı pravidla gramatiky.


54

Veˇta 3.3 Ke kazˇde´mu Turingovu stroji M lze sestrojit gramatiku G typu 0 takovou, zˇe L(M) = L(G).

✎

Du˚kaz: Budeme postupovat takto: • vygenerujeme dveˇ kopie te´hozˇ slova, • prvnı´ (hornı´) na konci generovańı´ pouzˇijeme jako vy´stup gramatiky, na druhe´ (spodnı´) budeme simulovat cˇinnost TS, • vy´stup gramatiky bude slozˇen pouze z termina´lnıćh symbolu˚ jen tehdy, pokud simulace na druhe´ kopii skoncˇ´ı ve stavu qaccept . Netermina´ly ma´me neˇkolika typu˚: • netermina´ly ve tvaru sloupcove´ho vektoru, jehozˇ hornı´ prvek ∈ T nebo je ε, • netermina´ly pro stav (zacˇ. q0 ) a zacˇa´tek a konec rˇeteˇzce $, • dalsˇ´ı netermina´ly bez prˇ´ıme´ho vztahu k TS (S, S 0 ). Pro lepsˇ´ı prˇedstavu se podı´va´me na fragment uka´zky odvozenı´: " #" #" #" #" #" #" # ε a a b b c c $ ⇒∗ aabbcc S ⇒∗ q0 $ a a b b c c Postupneˇ vytvorˇ´ıme pravidla gramatiky. 1. Vygenerujeme dveˇ kopie te´hozˇ slova: " # ε S0 S → q0 $ " # a S0 → S 0 pro kazˇde´ a ∈ Σ a S0 → $ 2. Simulujeme cˇinnost Turingova stroje: (a) pro δ(qi , a) = (qj , b, 1), a, b ∈ Γ, qi , qj ∈ Q vytvorˇ´ıme pravidlo " # " # x x qi → qj , pro x ∈ Σ ∪ {ε} a b

"


55

(b) pro δ(qi , a) = (qj , b, 0), a, b ∈ Γ, qi , qj ∈ Q vytvorˇ´ıme pravidlo " # " # x x qi → qj , pro x ∈ Σ ∪ {ε} a b (c) pro δ(qi , a) = (qj , b, −1), a, b ∈ Γ, qi , qj ∈ Q vytvorˇ´ıme pravidlo " # " # " #" # y x y x qi → qj , pro x, y ∈ Σ ∪ {ε}, c ∈ Γ c a c b (d) pro δ(qi , t) = (qj , b, 1), prˇ´ıp. δ(qi , $) = (qj , b, 1), b ∈ Γ, qi , qj ∈ Q vytvorˇ´ıme " # ε qi $ → qj $ b (e) pro δ(qi , t) = (qj , b, 0), prˇ´ıp. δ(qi , $) = (qj , b, 0), b ∈ Γ, qi , qj ∈ Q vytvorˇ´ıme " # ε qi $ → qj $ b (f) pro δ(qi , t) = (qj , b, −1), prˇ´ıp. δ(qi , $) = (qj , b, −1), b ∈ Γ, qi , qj ∈ Q vytvorˇ´ıme pravidlo " # " #" # y y ε qi $ → qj $, pro y ∈ Σ ∪ {ε}, c ∈ Γ c c b 3. Zakoncˇ´ıme derivaci (vytvorˇ´ı se termina´lnı´ slovo): (a) Posuneme qaccept na zacˇa´tek veˇtne´ formy: M qaccept → qaccept M pro vsˇechny netermina´ly M ∈ N (b) Tvorˇ´ıme termina´ly: " # a qaccept → a qaccept x (c) Mazˇeme vsˇe, co nevytvorˇ´ı termina´l: " # ε → qaccept qaccept x (d) Konec derivace:

qaccept $ → ε 2

Kapitola

4

Jazyky typu 1 V te´to kapitole se budeme zaby´vat trˇ´ıdou jazyku˚ generovanyćh gramatikami typu 1 Chomske´ho hierarchie. Nejdrˇ´ıv se podı´va´me na tvar gramatik, ktere´ mohou generovat tyto jazyky a vztah mezi nimi, da´le se budeme zaby´vat modely – stroji rozpozna´vajıćı´mi tyto gramatiky a take´ se budeme veˇnovat uza´veˇrovy´m vlastnostem jazyku˚ typu 1 Chomske´ho hierarchie.

4.1

Gramatiky typu 1

V kurzu Teorie jazyku˚ a automatu˚ I jsme si vysveˇtlili, zˇe trˇebazˇe gramatiky typu 1 jsou nezkracujıćı´, existuje jiny´ typ gramatik generujıćıćh tute´zˇ trˇ´ıdu jazyku˚ – gramatiky kontextove´. Definice 4.1 (Nezkracujıćı´ gramatika) Nezkracujıćı´ gramatika je takova´ gramatika, jejı´zˇ pravidla jsou ve tvaru

✍

α → β, kde |α| ≤ |β|, α ∈ (N ∪ T )∗ N (N ∪ T )∗ , β ∈ (N ∪ T )∗ Je prˇ´ıpustne´ take´ pravidlo S → ε, pokud ε je slovo jazyka, ktery´ gramatika generuje, S se nesmı´ vyskytovat na prave´ straneˇ zˇa´dne´ho pravidla. Definice 4.2 (Kontextova´ gramatika) Kontextova´ gramatika je gramatika s pravidly ve tvaru αAβ → αγβ, kde |γ| > 0, α, β, γ ∈ (N ∪ T )∗ Je prˇ´ıpustne´ take´ pravidlo S → ε, pokud ε je slovo jazyka, ktery´ gramatika generuje, S se nesmı´ vyskytovat na prave´ straneˇ zˇa´dne´ho pravidla. 56

✍


57

Je zrˇejme´, zˇe kazˇda´ kontextova´ gramatika je za´rovenˇ nezkracujıćı´, vyply´va´ to prˇ´ımo z tvaru pravidel. Platı´ vsˇak i opacˇna´ relace? Veˇta 4.1 Ke kazˇde´ nezkracujıćı´ gramatice G lze sestrojit kontextovou gramatiku G0 takovou, zˇe L(G0 ) = L(G).

✎

Du˚kaz: Kazˇde´ pravidlo typu

y

A1 A2 . . . Am → B1 B2 . . . Bn , ktere´ nema´ kontextovy´ tvar, nahradı´me mnozˇinou pravidel: A1 A2 A3 . . . Am → C1 A2 A3 . . . Am C1 A2 A3 . . . Am → C1 C2 A3 . . . Am C1 C2 A3 . . . Am → C1 C2 C3 . . . Am .. . C1 C2 . . . Cm−1 Am → C1 C2 . . . Cm−1 Cm Bm+1 . . . Bn C1 C2 . . . Cm−1 Cm Bm+1 . . . Bn → C1 . . . Cm−1 Bm . . . Bn C1 C2 . . . Cm−1 Bm Bm+1 . . . Bn → C1 . . . Bm−1 Bm . . . Bn .. . C1 B2 . . . Bn → B1 . . . Bn Kde Ci jsou noveˇ prˇidane´ netermina´ly, ktere´ se jinde nevyskytujı´.

2

Prˇı´klad 4.1 Vytvorˇ´ıme nezkracujıćı´ gramatiku pro jazyk L5 = {ww | w ∈ {a, b}∗ } S → XZa Za | XZb Zb | aa | bb | ε pokud w koncˇ´ı na a, zacˇ´ına´me prvnı´m pravidlem – . . . Za . . . Za pokud w koncˇ´ı na b, zacˇ´ına´me druhy´m pravidlem – . . . Zb . . . Zb XZa → aZa Xa | bZa Xb | aaXa | baXb v prvnı´ polovineˇ jsme vygenerovali a, posˇleme info do druhe´ – . . . aZa Xa . . . Za v prvnı´ polovineˇ jsme vygenerovali b, posˇleme info do druhe´ – . . . bZa Xb . . . Za Xa a → aXa Xa b → bXa Xb a → aXb Xb b → bXb

symbol Xa nebo Xb posı´la´me doprava

KAPITOLA 4 JAZYKY TYPU 1 Xa Za → Y aZa | aa Xb Za → Y bZa | ba aY → Y a bY → Y b Za Y → XZa

58

info doputovalo k zara´zˇce na konci slova – . . . aZa . . . Y aZa . . . bZa . . . Y bZa

symbol Y posı´la´me doleva – zpra´va „pokracˇuj v prvnı´ polovineˇ“ prˇekrocˇili jsme zara´zˇku na konci prvnı´ poloviny slova

Da´le tote´zˇ pro Zb mı´sto Za : XZb → aZb Xa | bZb Xb | abXa | bbXb Xa Zb → Y aZb | ab Xb Zb → Y bZb | bb Zb Y → XZb Uka´zka odvozenı´: S ⇒ XZa Za ⇒ aZa Xa Za ⇒ aZa Y aZa ⇒ aXZa aZa ⇒ abZa Xb aZa ⇒ ⇒ abZa aXb Za ⇒ abZa aY bZa ⇒ abZa Y abZa ⇒ abXZa abZa ⇒ abbXb abZa ⇒ ⇒ abbaXb bZa ⇒ abbabXb Za ⇒ abbabba

4.2

Kurodova norma´lnı´ forma pro gramatiky typu 1

(Kuroda normal form, KNF) Definice 4.3 (Kurodova norma´lnı´ forma pro gramatiky typu 1) Gramatika je v KNF, jestlizˇe vsˇechna jejı´ pravidla jsou ve tvaru

✍

A → BC AB → CD A → a A, B, C, D ∈ N , a ∈ T , prˇ´ıpadneˇ S → ε Veˇta 4.2 Ke kazˇde´ nezkracujıćı´ (i kontextove´) gramatice G lze sestrojit gramatiku G0 v Kurodoveˇ norma´lnı´ formeˇ takovou, zˇe L(G0 ) = L(G).

✎

Du˚kaz: Budeme postupovat takto:

"


59

• pravidla v bezkontextove´m tvaru: pouzˇijeme algoritmus pro prˇevod na Chomske´ho NF. • pravidla, ktera´ nejsou bezkontextove´ho typu: upravı´me pravidla podle na´sledujıćı´ho algoritmu. Vstup: nezkracujıćı´ gramatika bez jednoduchyćh pravidel typu X → Y,

X, Y ∈ N

1. Pro vsˇechna pravidla: • vsˇechny termina´ly (na leve´ i prave´ straneˇ pravidla) a ∈ T nahradı´me „pomocny´mi“ netermina´ly Na , • pro vsˇechny netermina´ly vytvorˇene´ v prˇedchozı´m bodu prˇida´me pravidlo Na → a. 2. Pravidla A → B1 B2 . . . Bn , n > 2 nahradı´me pravidly A → B1 X1 X1 → B2 X2 .. . Xn−2 → Bn−1 Bn 3. Pravidla A1 A2 . . . Am → B1 B2 . . . Bm , m > 2 nahradı´me pravidly A1 A2 → B1 X1 X1 A3 → B2 X2 .. . Xm−2 Am → Bm−1 Bm 4. Nezkracujıćı´ pravidla A1 A2 . . . Am → B1 B2 . . . Bn , 2 < m ≤ n nahradı´me pravidly A1 A2 → B1 X1 X1 A3 → B2 X2 .. . Xm−2 Am → Bm−1 Xm−1

Xm−1 → Bm Xm Xm → Bm+1 Xm+1 .. . Xn−2 → Bn−1 Bn 2


4.3

60

Linea´rneˇ ohranicˇeny´ automat

Tak jako jazyku˚m typu 0 mu˚zˇeme prˇirˇadit Turingu˚v stroj a naprˇ´ıklad konecˇny´ automat rozpozna´va´ pra´veˇ regula´rnı´ jazyky, k jazyku˚m typu 1 mu˚zˇeme prˇirˇadit linea´rneˇ ohranicˇeny´ automat (LOA, Lineary Bounded Automaton). Definici LOA prˇejı´ma´me z definice TS, jen prˇida´va´me za´kaz prˇepisu hranicˇnıćh symbolu˚. Definice 4.4 (Linea´rneˇ ohranicˇeny´ automat) Linea´rneˇ ohranicˇeny´ automat je jednopa´skovy´ (nedeterministicky´) Turingu˚v stroj M = (Q, Σ, Γ, δ, q0 , F ), ve ktere´m cˇtecı´ a za´pisova´ hlava nesmı´ beˇhem vy´pocˇtu prˇepsat hranicˇnı´ symboly $ pa´sky (tj. slovo nesmı´ by´t beˇhem vy´pocˇtu prodluzˇovańo).

✍

Definice 4.5 (Konfigurace linea´rneˇ ohranicˇene´ho automatu) Konfigurace linea´rneˇ ohranicˇene´ho automatu je (α, q, β), kde q je stav, na pa´sce je rˇeteˇzec αβ, cˇtecı´ a za´pisova´ hlava ukazuje na prvnı´ symbol rˇeteˇzce β.

✍

Prˇechod mezi konfiguracemi je definovań stejneˇ jako u Turingova stroje, jen je trˇeba zohlednit nemozˇnost prˇepisu hranicˇnıćh symbolu˚. Veˇta 4.3 Pro konkre´tnı´ linea´rneˇ ohranicˇeny´ automat M a dany´ vstup w0 existuje konecˇny´ pocˇet ru˚znyćh konfiguracı´.

✎

Du˚kaz: Protozˇe ma´me konecˇny´ pocˇet stavu˚, konecˇny´ pocˇet pa´skovyćh symbolu˚ a omezenou cˇa´st vstupnı´ pa´sky, platı´: jestlizˇe oznacˇ´ıme

"

d . . . de´lka pouzˇ´ıvane´ cˇa´sti pa´sky, s . . . pocˇet stavu˚ v Q, g . . . pocˇet prvku˚ pa´skove´ abecedy Γ, pak pocˇet vsˇech mozˇnyćh ru˚znyćh konfiguracı´ je d · s · g d (hlava mu˚zˇe by´t na d ru˚znyćh pozicıćh, naby´va´ hodnot s ru˚znyćh stavu˚, pocˇet vsˇech mozˇnyćh rˇeteˇzcu˚ nad abecedou Γ o de´lce d je g d ). 2 Pozna´mka: Rekurzı´vnı´ jazyky jsme definovali v definici 3.9 na straneˇ 49. Narozdı´l od rekurzı´vneˇ spocˇetnyćh jazyku˚ je lze zpracovat Turingovy´m strojem tak, zˇe pro

❁


61

jaky´koliv vstup vy´pocˇet skoncˇ´ı prˇechodem do neˇktere´ho koncove´ho stavu, bez prˇechodu do nekonecˇne´ smycˇky, a vy´pocˇet probı´ha´ na principu rekurze (rekurzı´vneˇ uplatnˇujeme δ funkci). Du˚sledek 4.4 LOA lze vzˇdy navrhnout tak, aby vy´pocˇet skoncˇil nad jaky´mkoliv vstupem. Proto jazyky, ktere´ jsou prˇijı´mańy neˇjaky´m LOA, jsou pra´veˇ rekurzı´vnı´ jazyky. Du˚kaz: Stacˇ´ı prˇi kazˇde´m kroku vy´pocˇtu LOA zkontrolovat, jestli se nenacha´zı´ v konfiguraci, ve ktere´ uzˇ byl drˇ´ıve. Pokud ano, vy´pocˇet v pu˚vodnı´m automatu se dostal do smycˇky a my mu˚zˇeme skoncˇit v chybove´m stavu qreject (vstup neprˇijmeme). Pokud pro kazˇdy´ vstup LOA najdeme pocˇet polıćˇek pa´sky, se ktery´mi beˇhem vy´pocˇtu bude pracovat cˇtecı´ a za´pisova´ hlava (tj. de´lka cˇa´sti pa´sky pouzˇite´ prˇi vy´pocˇtu, prostorova´ slozˇitost vy´pocˇtu automatu nad dany´m vstupem), zjistı´me, zˇe tato hodnota je linea´rneˇ za´visla´ na de´lce vstupu, tedy existuje prˇirozene´ cˇ´ıslo k takove´, zˇe de´lka pouzˇite´ cˇa´sti pa´sky je mensˇ´ı nezˇ k · |w|. Odtud je odvozen take´ na´zev tohoto automatu – automat s linea´rneˇ ohranicˇeny´m pracovnı´m prostorem. 2 Pozna´mka: V neˇkteryćh zdrojıćh je LOA definovań prˇ´ımo jako Turingu˚v stroj s linea´rneˇ ohranicˇeny´m pracovnı´m prostorem, a je tedy dovoleno pouzˇ´ıvat pro vy´pocˇet kazˇde´ho slova w nejvy´sˇe k · |w| polıćˇek pa´sky (tedy nejen pro k = 1). Veˇta 4.5 Jazyky typu 1 jsou pra´veˇ jazyky prˇijı´mane´ linea´rneˇ ohranicˇeny´mi automaty. Du˚kaz: („⇒“) Ma´me nezkracujıćı´ gramatiku G, ktera´ generuje zadany´ jazyk typu 1 L. Derivace v te´to gramatice je ve tvaru S ⇒ w1 ⇒ w2 ⇒ . . . wn , kde |wi | ≤ |wj | pro i < j. Sestrojı´me LOA M takto: 1. Na vstupu je slovo, o ktere´m chceme zjistit, zda je generovańo gramatikou G. 2. Na tento vstup budeme uplatnˇovat pravidla gramatiky takto: (a) nedeterministicky zvolı´me pravidlo gramatiky (α → β),

➠ "

❁ ✎ "


62

(b) najdeme v rˇeteˇzci na pa´sce neˇktery´ vy´skyt prave´ strany tohoto pravidla (β) – pokud je teˇchto vy´skytu˚ vıće, nedeterministicky mezi nimi jeden zvolı´me, (c) vy´skyt β prˇepı´sˇeme rˇeteˇzcem α, pokud je α kratsˇ´ı, posuneme to, co na´sleduje za β, doleva, aby zbytek pracovnı´ho slova navazoval na α. 3. Vy´pocˇet ukoncˇ´ıme: • ve stavu akceptovańı´ (qaccept ), pokud na pa´sce bude pouze startovacı´ symbol gramatiky a nic jine´ho, • ve stavu odmı´tnutı´ slova (qreject , qerror ), pokud je na pa´sce neˇco jine´ho a jizˇ nelze pouzˇ´ıt zˇa´dne´ pravidlo gramatiky. Je zrˇejme´, zˇe takto vytvorˇeny´ LOA vytva´rˇ´ı derivaci slova podle gramatiky G zprava doleva (a tedy konstruuje derivacˇnı´ strom pro toto slovo zdola nahoru ke korˇeni stromu ohodnocene´mu startovacı´m symbolem) a ve stavu akceptovańı´ skoncˇ´ı pra´veˇ na ta slova, ktera´ generuje gramatika G. 2 Du˚kaz: („⇐“) Je dań LOA M. Vytvorˇ´ıme nezkracujıćı´ gramatiku G podobneˇ jako v obdobne´m du˚kazu pro Turingovy stroje a gramatiky typu 0, jen musı´me pravidla upravit tak, aby byla nezkracujıćı´. 1. V gramatice G nejdrˇ´ıv vygenerujeme rˇeteˇzec netermina´lu˚, ktery´ prˇedstavuje dvojici slov na vstupu simulovane´ho LOA. Oproti gramatice typu 0 musı´me symboly pro zacˇa´tek a konec pracovnı´ cˇa´sti pa´sky a take´ symbol pro stav automatu umı´stit dovnitrˇ netermina´lu˚ pro symboly slova, abychom nebyli nuceni na konci vy´pocˇtu pouzˇ´ıt epsilonova´ pravidla. " # " # a ε S→ S0 $, q0 , $ $, q0 , a " # " # a a S0 → S0 pro kazˇde´ a ∈ Σ a, $ a Dostaneme rˇeteˇzec netermina´lu˚ # #" #" # " " ak a3 a2 a1 ... ak , $ a3 a2 $, q0 , a1

"


63

2. Simulujeme pru˚beˇh vy´pocˇtu LOA: Naprˇ. pro kazˇdou cˇa´st δ funkce typu δ(qi , a) 3 (qj , b, 1) " #" # " #" # x y x y → pro kazˇde´ c ∈ Γ − {$} qi , a c b qj , c Podobneˇ pro ostatnı´ smeˇry pohybu cˇtecı´ a za´pisove´ hlavy, navıć musı´me osˇetrˇit praći s netermina´ly, ktere´ obsahujı´ hranicˇnı´ znaky $. 3. Ukoncˇenı´ vy´pocˇtu: " #" # " #" # x y x y → a qacc , b qacc , a b " #" # " # x y y →x $, a qacc , b K, b " #" # " # x y y →x K, a b K, b " #" # x y → xy K, a b, $ Posuneme qacc doprˇedu na zacˇa´tek rˇeteˇzce, pak prˇejdeme do ukoncˇujıćı´ho stavu K a postupneˇ vsˇechny netermina´ly prˇepı´sˇeme na termina´ly. 2

4.4

Uza´veˇrove´ vlastnosti jazyku˚ typu 1

Veˇta 4.6 Trˇ´ıda jazyku˚ typu 1 je uzavrˇena vzhledem k operacı´m sjednocenı´, zrˇeteˇzenı´, iterace, pozitivnı´ iterace, homomorfismu, substituce.

✎

Du˚kaz: Stejneˇ jako u bezkontextovyćh jazyku˚, pomocı´ gramatik. Naprˇ´ıklad pro sjednocenı´ prˇida´me navıć pravidlo S → S1 | S2 , kde S je noveˇ prˇidany´ symbol, S1 je startovacı´ symbol prvnı´ gramatiky a S2 je startovacı´ symbol druhe´ gramatiky. 2

"

Veˇta 4.7 Trˇ´ıda jazyku˚ typu 1 je uzavrˇena vzhledem k operaci pru˚niku.

✎


64

Du˚kaz: Ma´me dva LOA M1 , M2 . Sestrojı´me LOA M, ktery´ bude postupneˇ simulovat vy´pocˇet obou teˇchto automatu˚, a pokud oba skoncˇ´ı s akceptovańı´m vstupnı´ho slova, toto slovo take´ akceptuje.

"

1. Na vstupnı´ pa´sce pro akceptovańı´ slova w bude rˇeteˇzec $w#w$. 2. Nejdrˇ´ıv M simuluje na prvnı´ kopii slova w vy´pocˇet stroje M1 s tı´m, zˇe hranicˇnı´ symboly jsou $ a #. 3. Pokud simulovany´ vy´pocˇet skoncˇ´ı ve stavu akceptovańı´ slova, posune cˇtecı´ a za´pisovou hlavu na prvnı´ symbol za znakem # (tj. na prvnı´ symbol druhe´ kopie slova w) a simuluje vy´pocˇet stroje M2 . 4. Pokud tento vy´pocˇet skoncˇ´ı ve stavu akceptovańı´, M akceptuje slovo w. 2 Veˇta 4.8 Trˇ´ıda jazyku˚ typu 1 je uzavrˇena vzhledem k operaci doplnˇku.

✎

Du˚kaz lze prove´st pomocı´ DeMorganovyćh pravidel nebo konstrukcˇneˇ. Du˚kaz pomocı´ DeMorganovyćh pravidel mu˚zˇeme nechat na cˇtena´rˇi, konstrukcˇnı´ du˚kaz je jednoduchy´: Du˚kaz: LOA lze vzˇdy sestrojit tak, aby jeho vy´pocˇet byl konecˇny´. Proto aby prˇijı´mal doplneˇk pu˚vodnı´ho jazyka, pouze zameˇnı´me akceptujıćı´ a chybovy´ stav. 2

"

Kapitola

5

L-syste´my V te´to kapitole si prˇedstavı´me biologicky motivovany´ typ syste´mu, ktery´ nepatrˇ´ı do Chomske´ho hierarchie, L-syste´my. Sezna´mı´me se zde s pouzˇitı´m paralelismu v tomto forma´lnı´m syste´mu, s jeho za´kladnı´mi typy a take´ s mozˇnostmi prakticke´ho vyuzˇitı´.

5.1

Paralelnı´ odvozovańı´

Gramatiky Chomske´ho hierarchie pracujı´ vzˇdy sekvencˇneˇ. Obecneˇ vsˇak mu˚zˇeme pouzˇ´ıvat i paralelnı´ mo´d odvozenı´, kdy je za urcˇityćh podmıńek dovoleno zpracova´vańı´ vıće mı´st v prˇepisovane´m sloveˇ. Mezi prvnı´mi, kterˇ´ı ve sve´ praći pouzˇ´ıvali paralelnı´ mo´d odvozenı´, byl mad’arsky´ biolog Aristid Lindenmayer (1925–1989). V roce 1968 publikoval cˇlańek, ve ktere´m prˇedstavil mozˇnost vyuzˇitı´ matematickyćh modelu˚ pro simulaci neˇkteryćh vy´vojovyćh procesu˚ v prˇ´ırodeˇ. Jeho model byl nazvań Lindenmayerovy syste´my (Lsyste´my) a jeho vlastnosti za´visejı´ prˇedevsˇ´ım na urcˇenı´ pro simulace deˇju˚ v prˇ´ırodeˇ – v prˇ´ırodeˇ mnoho deˇju˚ probı´ha´ paralelneˇ (deˇlenı´ buneˇk, spolupraće mravencu˚, ru˚st tra´vy na louce, apod.) a soucˇa´stı´ prˇ´ırody jsou i „meziprodukty“, nejen konecˇny´ vy´sledek odvozenı´. ´ cˇelem bylo shrnout do jednoho celku strukturu organismu a za´rovenˇ pravidla U pro jeho vy´voj tak, aby pravidla mohla pu˚sobit obdobneˇ jako je beˇzˇne´ v prˇ´ırodeˇ, paralelneˇ (za´rovenˇ – bunˇky prˇi sve´m deˇlenı´ jedna na druhou necˇekajı´). Jeho zˇaći o neˇkolik let pozdeˇji vyvinuli zpu˚sob vizualizace L-syste´mu˚ prˇedevsˇ´ım pro simulaci ru˚stu rostlin.

65

KAPITOLA 5 L-SYSTE´MY

66

Matematici pozdeˇji zacˇali L-syste´my pouzˇ´ıvat pro studium sobeˇpodobnosti (male´ cˇa´sti objektu jsou podobne´ objektu cele´mu, naprˇ. veˇtvicˇka na stromeˇ vypada´ jako zmensˇeny´ strom samotny´). L-syste´my majı´ tyto vlastnosti: • pouzˇ´ıva´ se pouze jedina´ abeceda syste´mu, nerozlisˇujeme termina´lnı´ a netermina´lnı´ abecedu1 , • vy´voj probı´ha´ v prostrˇedı´, v prostrˇedı´ je prˇepisovane´ slovo – posloupnost symbolu˚ abecedy, kterou take´ nazy´va´me stav prostrˇedı´, • pro kazˇdy´ symbol abecedy syste´mu musı´ existovat alesponˇ jedno pravidlo (obvykle bezkontextove´), pravidlu˚m se rˇ´ıka´ vy´vojova´ pravidla, • vy´vojova´ pravidla pracujı´ paralelneˇ, • v kazˇde´m kroku odvozenı´ jsou prˇepsańy vzˇdy vsˇechny symboly, ktere´ se pra´veˇ v prostrˇedı´ nacha´zejı´, a to ktery´mkoliv (na´hodneˇ vybrany´m) pravidlem pro tento symbol, • axiom, tedy pocˇa´tecˇnı´ slovo odvozovańı´, mu˚zˇe by´t oproti startovacı´mu symbolu Chomske´ho gramatik jakkoliv dlouhe´ slovo, • odvozenı´ je teoreticky nekonecˇne´, ale mu˚zˇeme si stanovit maxima´lnı´ de´lku odvozovańı´. Pokud do definice syste´mu nezahrneme axiom, ale pouze abecedu a mnozˇinu vy´vojovyćh pravidel, hovorˇ´ıme o L-sche´matu, po zahrnutı´ axiomu do definice jde o L-syste´m.

5.2

0L-syste´my

L-syste´my majı´ hodneˇ variant. Za´kladnı´ vy´sˇe popsana´ varianta s jedinou abecedou a bezkontextovy´mi vy´vojovy´mi pravidly se nazy´va´ 0L-syste´my. 0L-sche´ma pak ma´ tvar G = (V, P ), kde V je abeceda syste´mu a P je mnozˇina vy´vojovyćh pravidel, 0L-syste´m ma´ tvar G = (V, P, ω0 ) – navıć je axiom ω0 ∈ V ∗ . Do jazyka generovane´ho 0Lsyste´mem jsou rˇazeny vsˇechny stavy prostrˇedı´, tedy vlastneˇ vsˇechny cˇleny ktere´koliv derivace z axiomu. 1

Existujı´ vsˇak odvozene´ modely, ve kteryćh je termina´lnı´ abeceda odlisˇena.

✍


67

Definice 5.1 (0L-sche´ma) 0L-sche´ma je definovańo jako usporˇa´dana´ dvojice S0 = (V, P ), kde • Σ je nepra´zdna´ konecˇna´ abeceda syste´mu, • P je mnozˇina pravidel bezkontextove´ho typu P ⊆ V × V ∗ (naprˇ. a → bac). Definice 5.2 (0L-syste´m) 0L-syste´m je definovań jako G0 = (V, P, ω0 ), kde

✍

• (V, P ) je 0L-sche´ma, • ω0 je axiom (startovacı´ slovo). Krok odvozenı´ zde nebudeme forma´lneˇ definovat, na´m bude stacˇit zatı´m jen informace, zˇe se jedna´ o relaci ⇒G0 takovou, zˇe v kazˇde´m kroku odvozenı´ prˇepisujeme vsˇechny symboly prˇepisovane´ho slova, kazˇdy´ z teˇchto symbolu˚ ktery´mkoliv pravidlem z mnozˇiny P . Reflexivnı´ a tranzitivnı´ uza´veˇr relace ⇒G0 budeme oznacˇovat ⇒∗G0 . Definice 5.3 (Jazyk 0L-syste´mu) Jazyk generovany´ 0L-syste´mem G0 = (V, P, ω0 ) je ∗

L(G0 ) = {w ∈ V |

ω0 ⇒∗G0

w}.

Prˇı´klad 5.1 Na´sledujıćı´ 0L-syste´m nad jednoprvkovou abecedou mu˚zˇeme cha´pat jako jednoduchou simulaci deˇlenı´ buneˇk. G0 = (V, P, ω0 ), kde V = {a}, P = {a → aa}, ω0 = a Uka´zka derivace: a ⇒G0 aa ⇒G0 aaaa ⇒G0 a8 ⇒G0 a16 ⇒G0 a32 ⇒G0 . . . Jazykem tohoto 0L-syste´mu je n o n L 4 = a2 n ≥ 0

✍

Tento jazyk nenı´ bezkontextovy´, tedy nelze ho generovat zˇa´dnou bezkontextovou gramatikou.


68

Prˇı´klad 5.2 G0 = ({a}, {a → aa}, aaa}

Uka´zka odvozenı´: aaa ⇒G0 aaaaaa ⇒G0 a12 ⇒G0 a24 ⇒G0 . . . Tento 0L-syste´m generuje kontextovy´ jazyk n

L(G0 ) = L20 = {a3·2 | n ≥ 1}

Mnozˇinu vsˇech 0L-syste´mu˚ budeme oznacˇovat zkratkou 0L, tedy fakt, zˇe G0 je 0L-syste´m, mu˚zˇeme napsat jako G0 ∈ 0L. Trˇ´ıdu (mnozˇinu) jazyku˚ generovanyćh 0L-syste´my znacˇ´ıme L (0L), jak je v teˇchto skriptech pro trˇ´ıdy jazyku˚ zvykem, a tedy fakt, zˇe jazyk L20 patrˇ´ı do te´to trˇ´ıdy, lze zapsat jako L20 ∈ L (0L). Veˇta 5.1 Jazyk L21 = {a, aa} nelze generovat zˇa´dny´m 0L-syste´mem, tedy L21 ∈ / L (0L). Du˚kaz: Prˇedpokla´dejme, zˇe existuje 0L-syste´m G0 = (Σ, P, ω0 ) generujıćı´ jazyk L21 . Pak axiomem ω0 musı´ by´t neˇktere´ ze slov jazyka (protozˇe ma´me jen jednu abecedu Σ). Kdyzˇ zvolı´me jako axiom rˇeteˇzec a, musı´me mı´t mozˇnost vygenerovat rˇeteˇzec aa, tedy musı´ existovat derivace a ⇒∗G0 aa. To ale znamena´, zˇe lze symbol a zdvojit, a proto by do jazyka musely patrˇit i rˇeteˇzce aaaa, aaaaaaaa, . . . ⇒ axiomem nemu˚zˇe by´t rˇeteˇzec a. Kdyzˇ zvolı´me jako axiom rˇeteˇzec aa, musı´me mı´t mozˇnost vygenerovat rˇeteˇzec a, tedy musı´ existovat derivace aa ⇒∗G0 a. To ale znamena´, zˇe musı´ existovat mozˇnosti derivace

✎ "

a ⇒∗G0 a a ⇒∗G0 ε a proto by do jazyka musel patrˇit i rˇeteˇzec ε, tedy axiomem nemu˚zˇe by´t rˇeteˇzec aa. Axiom musı´ vzˇdy patrˇit do jazyka, tedy nenasˇli jsme 0L-syste´m, ktery´ by generoval tento jazyk, L21 ∈ / L (0L). 2 Du˚sledek 5.2 Generativnı´ sı´la 0L-syste´mu˚ je neporovnatelna´ s generativnı´ sı´lou bezkontextovyćh gramatik, i kdyzˇ pouzˇ´ıva´ stejny´ typ pravidel – existujı´ bezkontextove´ jazyky, ktere´ nepatrˇ´ı do trˇ´ıdy L (0L) a existujı´ jazyky generovane´ 0L-syste´my, ktere´ nejsou bezkontextove´. Proto paralelnı´ zpu˚sob praće za´sadneˇ meˇnı´ vlastnosti gramatik.

➠


69

Zapisujeme L (0L)

L (CF )

(5.1)

0L-syste´my majı´ neˇktere´ zajı´mave´ vlastnosti ty´kajıćı´ se vy´pocˇtu˚ – v prˇ´ıkladu do teˇchto vlastnostı´ trochu nahle´dneme: Prˇı´klad 5.3 GF = ({a, b}, {a → ab, b → a}, b) Uka´zka odvozenı´: b ⇒GF a ⇒GF ab ⇒GF aba ⇒GF abaab ⇒GF abaababa ⇒GF abaababaabaab ⇒GF . . . Pro de´lky slov platı´: |ω0 | = 1 |ω1 | = 1 |ω2 | = 2 |ω3 | = 3 |ω4 | = 5 |ω5 | = 8 |ω6 | = 13 . . . Prvky derivace jsou rˇeteˇzce s de´lkou Fibbonacciho cˇ´ısel, tedy |ωi | + |ωi+1 | = |ωi+2 | , i ≥ 0.

5.3

E0L-syste´my

E0L-syste´m ma´ oproti 0L-syste´mu navıć termina´lnı´ abecedu ∆ ⊆ V . Do jazyka generovane´ho E0L-syste´mem rˇadı´me pouze ty cˇleny derivacı´, ktere´ se skla´dajı´ jen z termina´lnıćh symbolu˚. Termina´lnı´ slovo se mu˚zˇe da´le vyvı´jet, soucˇa´stı´ jedne´ derivace by´va´ i vıće termina´lnıćh slov. Z biologicke´ho hlediska lze roli termina´lnı´ abecedy cha´pat jako filtr vybı´rajıćı´ pouze ty stavy prostrˇedı´, ktere´ na´s z neˇjake´ho du˚vodu zajı´majı´ – cˇleny derivace, ktere´ obsahujı´ pouze prvky termina´lnı´ abecedy, patrˇ´ı do jazyka generovane´ho syste´mem, kdezˇto ty cˇleny derivace, ktere´ obsahujı´ nejmeńeˇ jeden symbol nepatrˇ´ıcı´ do termina´lnı´ abecedy, do jazyka generovane´ho syste´mem nepatrˇ´ı.


70

Definice 5.4 (E0L-sche´ma) E0L-sche´ma je definovańo jako SE = (V, ∆, P ), kde • V je nepra´zdna´ konecˇna´ abeceda syste´mu,

✍

• ∆ je nepra´zdna´ termina´lnı´ abeceda syste´mu, ∆ ⊆ V , • P je mnozˇina pravidel bezkontextove´ho typu P ⊆ V × V ∗ . Definice 5.5 (E0L-syste´m) E0L-syste´m je definovań jako GE = (V, ∆, P, ω0 ), kde • (V, ∆, P ) je E0L-sche´ma,

✍

• ω0 je axiom (startovacı´ slovo). Krok odvozenı´ je stejneˇ urcˇen jako u 0L-syste´mu˚. Definice 5.6 (Jazyk E0L-syste´mu) Jazyk generovany´ E0L-syste´mem GE urcˇeny´m jako GE = (V, ∆, P, ω0 ) je L(GE ) = {w ∈ ∆∗ | ω0 ⇒∗ w}. Prˇı´klad 5.4 Na´sledujıćı´ E0L-syste´m GE generuje jazyk L19 = L2 − {ε} = {an bn cn | n ≥ 1} Stejneˇ jako v prˇ´ıkladu 5.1 jde o jazyk, ktery´ nenı´ bezkontextovy´. GE = (V, ∆, P, ω0 ), kde V = {A, B, C, A0 , B 0 , C 0 , F, a, b, c}, ∆ = {a, b, c}, ω0 = ABC, mnozˇina P obsahuje tato vy´vojova´ pravidla: A → AA0 | a A0 → A0 | a a → F F → F 0 0 0 B → BB | b B → B |b b → F 0 0 0 C → CC | c C → C |c c → F Uka´zka dvou derivacı´, z nichzˇ jen prvnı´ vygeneruje termina´lnı´ slovo: ABC ⇒GE AA0 BB 0 CC 0 ⇒GE AA0 A0 BB 0 B 0 CC 0 C 0 ⇒GE aaabbbccc ⇒GE F 6 ⇒GE . . . ABC ⇒GE AA0 BB 0 CC 0 ⇒GE AA0 aBB 0 B 0 CC 0 C 0 ⇒GE aaF bbbccc ⇒GE ⇒GE F F F F F F F F F ⇒GE . . . V druhe´ derivaci se nikdy nedostaneme ke slovu, ktere´ se skla´da´ pouze z termina´lnıćh symbolu˚, tedy ke slovu˚m jazyka generovane´ho tı´mto syste´mem se dostaneme jen tak, zˇe pravidla generujıćı´ neˇktery´ termina´lnı´ symbol (a, b, c) pouzˇijeme pro vsˇechny symboly v prˇepisovane´m sloveˇ za´rovenˇ. Symbol F zde slouzˇ´ı pro synchronizaci generovańı´ termina´lnıćh symbolu˚ a, b, c tak, aby jich byl ve sloveˇ vzˇdy stejny´ pocˇet.

✍


71

✎

Veˇta 5.3 E0L-syste´my jsou silneˇjsˇ´ı nezˇ bezkontextove´ gramatiky, tj. L (CF ) ⊂ L (E0L)

(5.2)

Du˚kaz: Algoritmus vytvorˇenı´ E0L-syste´mu ekvivalentnı´ho k zadane´ bezkontextove´ gramatice zde nebudeme prˇesneˇ probı´rat, ale cˇtena´rˇ si ho jisteˇ sa´m cely´ domyslı´ s malou na´poveˇdou – kazˇdou sadu pravidel pro stejny´ netermina´l A → α1 | α2 | . . . v bezkontextove´ gramatice nahradı´me sadou pravidel v E0L-syste´mu A → A | α1 | α2 | . . ., cˇ´ımzˇ zajistı´me mozˇnost „sekvencˇnı´ho“ odvozenı´ i prˇi pouzˇitı´ paralelismu. Naprˇ´ıklad jazyk generovany´ E0L-syste´mem v prˇ´ıkladu 5.4 nenı´ bezkontextovy´, platı´ L19 ∈ L (E0L) − L (CF ). Proto platı´, zˇe E0L-syste´my jsou silneˇjsˇ´ı nezˇ bezkontextove´ gramatiky, trˇebazˇe se od nich lisˇ´ı vlastneˇ jen postupem derivovańı´ (paralelnı´m). 2 Prˇı´klad 5.5 GE = ({A, a}, {a}, {A → a, A → aa, a → a}, A)

"

Uka´zky odvozenı´: A ⇒GE a A ⇒GE aa Generovany´ jazyk je L21 = {a, aa}

✎

Veˇta 5.4 E0L-syste´my jsou silneˇjsˇ´ı nezˇ 0L-syste´my, tedy platı´ L (0L) ⊂ L (E0L)

(5.3)

Du˚kaz: 0L-syste´my mu˚zˇeme bra´t jako specia´lnı´ prˇ´ıpad E0L-syste´mu˚, kde ∆ = V . Tı´m je dańa relace L (0L) ⊆ L (E0L). Fakt, zˇe jde o vlastnı´ podmnozˇinu (tj. zˇe existujı´ jazyky generovane´ E0L-syste´my, ktere´ nelze generovat zˇa´dny´m 0L-syste´mem), dokazuje jazyk L21 ∈ L (E0L) − L (0L). 2

"


5.4

72

T0L-syste´my

T0L-syste´m zı´ska´me z 0L-syste´mu, kdyzˇ pravidla rozdeˇlı´me do tabulek a stanovı´me, zˇe v jednom kroku derivace se pouzˇijı´ pravidla z jedine´ vybrane´ tabulky. T0L-syste´m je tedy urcˇen abecedou, sadou tabulek T obsahujıćıćh pravidla (ta nahrazuje mnozˇinu pravidel P ). Definice 5.7 (T0L-sche´ma) T0L-sche´ma je definovańo jako ST = (V, T ), kde

✍

• V je nepra´zdna´ konecˇna´ abeceda syste´mu, • T je mnozˇina tabulek obsahujıćıćh pravidla bezkontextove´ho typu P ⊆ V × V ∗ . Definice 5.8 (T0L-syste´m) T0L-syste´m je definovań jako GT = (V, T , ω0 ), kde

✍

• (V, T ) je T0L-sche´ma, • ω0 je axiom (startovacı´ slovo). Krok odvozenı´ znacˇeny´ ⇒GT se prova´dı´ na´sledovneˇ: • vybereme si neˇkterou tabulku z mnozˇiny tabulek T , • prˇi odvozenı´ postupujeme stejneˇ jako u 0L-syste´mu (tj. vsˇechny symboly prˇepisujeme), pouzˇijeme vsˇak pouze pravidla z jedine´ vybrane´ tabulky. Definice 5.9 (Jazyk T0L-syste´mu) Jazyk generovany´ T0L-syste´mem GE = (V, T , ω0 ) je L(GT ) = {w ∈ V ∗ | ω0 ⇒∗GT w}. Prˇı´klad 5.6 GT = ({a}, {T1 , T2 }, a), kde T1 = {a → aa}, T2 = {a → ε} Uka´zka odvozenı´: a ⇒GT aa ⇒GT aaaa ⇒GT ε (pouzˇili jsme dvakra´t prvnı´ tabulku, pak jednou druhou tabulku). Generujeme tento o n jazyk: 2n L22 = L4 ∪ {ε} = a n ≥ 0 ∪ {ε}

✍


73

Kdybychom shrnuli obeˇ tabulky T0L-syste´mu z prˇ´ıkladu 5.6 do jedne´ a vytvorˇili tak pouhy´ 0L-syste´m, vygenerovany´ jazyk by byl a∗ . Pozna´mka: Da´ se doka´zat, zˇe L22 ∈ / L (0L) (trˇebazˇe jazyk bez prˇidańı´ ε by pro 0Lsyste´m nebyl proble´m), protozˇe axiom musı´ obsahovat alesponˇ jeden znak a tedy prˇidańı´ pra´zdne´ho slova do abecedy by vyzˇadovalo „zkracujıćı´“ pravidlo a → ε, ktere´ by ovsˇem udeˇlalo v odvozenı´ paseku – vznikl by jazyk a∗ . Veˇta 5.5 Ke kazˇde´mu 0L-syste´mu lze sestrojit T0L-syste´m, ktery´ generuje tenty´zˇ jazyk, navıć, T0L-syste´my jsou silneˇjsˇ´ı nezˇ 0L-syste´my: L (0L) ⊂ L (T 0L)

✎

(5.4)

Du˚kaz: Postup prˇevodu 0L-syste´mu na T0L-syste´m je jednoduchy´ – prosteˇ vsˇechna pravidla 0L-syste´mu shrneme do jedine´ tabulky, ta se pouzˇije v kazˇde´m kroku odvozenı´. Vlastnı´ podmnozˇinu lze doka´zat naprˇ´ıklad pomocı´ jazyka L22 ∈ L (T 0L) − L (0L). 2 Veˇta 5.6 Generativnı´ sı´la T0L-syste´mu˚ je neporovnatelna´ s generativnı´ sı´lou bezkontextovyćh gramatik: L (T 0L)

L (CF ) (5.5) Du˚kaz: Do mnozˇiny L (T 0L) − L (CF ) patrˇ´ı naprˇ´ıklad jazyk n o 2n L4 = a n ≥ 0

❁

(v prˇ´ıkladu 5.1 na straneˇ 67 je generovań 0L-syste´mem, a tedy je mozˇno ho generovat i T0L-syste´mem). Do mnozˇiny L (CF ) − L (T 0L) zase mu˚zˇeme zarˇadit jazyk L1 = {an bn | n ≥ 1} (kdyzˇ pocˇet znaku˚ roste pomaleji nezˇ exponencia´lneˇ, potrˇebovali bychom ε-pravidlo a → ε, a tote´zˇ i pro b, trˇeba i v jine´ tabulce nezˇ exponencia´lnı´ pravidlo a → aa; jenzˇe kdyzˇ existuje ε-pravidlo, pak se do jazyka dostane i pra´zdne´ slovo, cozˇ do L1 nepatrˇ´ı). 2

"

✎ "


5.5

74

ET0L-syste´my

ET0L-syste´my jsou kombinace E0L a T0L-syste´mu˚, tedy ma´me termina´lnı´ abecedu a pravidla rozdeˇlena´ do tabulek. Definici si cˇtena´rˇ mu˚zˇe vytvorˇit sa´m z definic E0La T0L-syste´mu˚. Prˇı´klad 5.7 GET = ({A, B, C, a, b, c}, {a, b, c}, {T1 , T2 , T3 }, ABC), kde T1 = {A → Aa, B → Bb, C → Cc, a → a, b → b, c → c}, T2 = {A → a, B → b, C → c, a → a, b → b, c → c} T3 = {A → ε, B → ε, C → ε, a → ε, b → ε, c → ε}

Uka´zka odvozenı´: ABC ⇒GET AaBbCc ⇒GET AaaBbbCcc ⇒GET aaabbbccc Generovany´ jazyk je L2 = {an bn cn | n ≥ 0}

Prˇi generovańı´ jazyka L2 byly plneˇ vyuzˇity vy´hody ET0L-syste´mu – oddeˇlenı´ termina´lnı´ abecedy pro ru˚st de´lky slova, ktery´ nenı´ exponencia´lnı´, a rozdeˇlenı´ do tabulek pro synchronizaci de´lky vsˇech trˇ´ı cˇa´stı´ slova a navıć pro vygenerovańı´ pra´zdne´ho slova. Tento jazyk nelze vygenerovat zˇa´dny´m 0L-syste´mem, E0L-syste´mem ani T0L-syste´mem. Du˚kazy na´sledujıćıćh vztahu˚ jsou pomeˇrneˇ jednoduche´, proto je necha´me na cˇtena´rˇi (vlastneˇ vyply´vajı´ z vlastnostı´ drˇ´ıve definovanyćh jednodusˇsˇ´ıch L-syste´mu˚):

✎

Veˇta 5.7 L (0L) ⊂ L (ET 0L)

(5.6)

L (E0L) ⊂ L (ET 0L)

(5.7)

L (T 0L) ⊂ L (ET 0L)

(5.8)

L (CF ) ⊂ L (ET 0L)

(5.9)

Existujı´ i dalsˇ´ı varianty L-syste´mu˚ vcˇetneˇ syste´mu˚ pracujıćıćh s kontextem nebo stochastickyćh L-syste´mu˚.


5.6

75

Mozˇnosti vyuzˇitı´ L-syste´mu˚ v grafice

L-syste´my se v praxi vyuzˇ´ıvajı´ prˇedevsˇ´ım v grafice, kde slouzˇ´ı k modelovańı´ a generovańı´ tzv. frakta´lu˚2 . Pouzˇ´ıvajı´ se naprˇ´ıklad ve filmove´m pru˚myslu pro generovańı´ realistickyćh „hromadnyćh“ vy´jevu˚, jako je naprˇ´ıklad les stromu˚ nebo oblaka na nebi. Aby tyto vy´jevy vypadaly realisticky, lze do jejich generovańı´ zane´st i prvek na´hody – tak vznikly stochasticke´ L-syste´my, kde je kazˇde´mu pravidlu prˇirˇazeno cˇ´ıslo z intervalu od 0 do 1 urcˇujıćı´ pravdeˇpodobnost pouzˇitı´ tohoto pravidla, soucˇet hodnot pravdeˇpodobnostı´ pravidel se stejnou levou stranou musı´ by´t 1. Prˇi graficke´ reprezentaci L-syste´mu˚ symbol F urcˇuje cˇa´ru o zadane´ de´lce, ktera´ se ma´ vykreslit a symboly + a − znamenajı´ pootocˇenı´ doprava nebo doleva o zadany´ u´hel. Podle axiomu a pravidel se provede urcˇity´ pocˇet odvozenı´ a vy´sledny´ rˇeteˇzec (stav prostrˇedı´) se pak graficky interpretuje. Na obra´zku 5.1 na straneˇ 76 je uka´zka neˇkolika jednoduchyćh frakta´lu˚. Prˇı´klad 5.8 Frakta´l na obra´zku 5.1d se nazy´va´ Kochova vlocˇka a byl vytvorˇen L-syste´mem s axiomem F + + F + + F a pravidlem F → F − F + + F − F postupneˇ cˇtyrˇmi pru˚chody: F ++F ++F ⇒ F −F ++ F −F ++ F −F ++ F −F ++ F −F ++ F −F ⇒ . . . (uzˇ trˇetı´ cˇlen derivace se skla´da´ ze 112 symbolu˚, tedy ho neuva´dı´me).

To jsou ovsˇem jen jednoduche´ prˇ´ıklady. Existuje vıće ru˚znyćh zpu˚sobu˚ jak do obra´zku zapracovat barvy, na´hodnost, kontext apod. Neˇktere´ programy pro vytva´rˇenı´ velmi pu˚sobivyćh frakta´lu˚ mu˚zˇeme najı´t take´ na internetu, stacˇ´ı do vyhleda´vacˇe zadat naprˇ´ıklad rˇeteˇzec L-systems nebo L-syste ´my .

2

Frakta´l je sobeˇpodobny´ u´tvar, ktery´ je velmi slozˇiteˇ tvarovany´ a prˇesto je reprezentovań velmi jednoduchou formou (trˇeba neˇkolika pravidly 0L-syste´mu). To, zˇe je u´tvar sobeˇpodobny´, znamena´, zˇe detaily u´tvaru v ru˚znyćh rozlisˇenıćh jsou podobne´ u´tvaru cele´mu.


76

(a)

(b)

(c)

(d)

Obra´zek 5.1: Neˇkolik frakta´lu˚ vygenerovanyćh pomocı´ L-Syste´mu˚

Kapitola

6

Forma´lnı´ syste´my V te´to kapitole se podı´va´me trochu da´le za pouhe´ za´klady, ktery´mi jsme se dosud zaby´vali. Nejdrˇ´ıv probereme ru˚zne´ typy derivacı´ v gramatikaćh a potom si popı´sˇeme za´kladnı´ vlastnosti gramatik a gramatickyćh syste´mu˚, ktere´ nepatrˇ´ı do Chomske´ho hierarchie.

6.1

Derivace v gramatikaćh

Existuje mnoho ru˚znyćh typu˚ derivacı´ v gramatikaćh, nejbeˇzˇneˇjsˇ´ı jsou tyto: • Sekvencˇnı´ postup – sekvencˇnı´ gramatiky (naprˇ´ıklad gramatiky v Chomske´ho hierarchii): v kazˇde´m kroku derivace je vybrańo a pouzˇito jedno pravidlo gramatiky na jeden netermina´l. • Paralelnı´ postup – paralelnı´ gramatiky (naprˇ. Lindenmayerovy syste´my): v kazˇde´m kroku derivace jsou najednou prˇepsańy vsˇechny netermina´ly ve sloveˇ, mohou by´t paralelneˇ pouzˇita ru˚zna´ pravidla, jedno pravidlo i vıćekra´t na ru˚znyćh mı´stech. • Sekvencˇneˇ-paralelnı´ postup – kombinace obou prˇedchozıćh, naprˇ. v gramatice vybereme jedno pravidlo a to pouzˇijeme vsˇude v generovane´m sloveˇ, kde je to mozˇne´ (tj. na vıće mı´stech), tedy pravidla vybı´ra´me sekvencˇneˇ a pouzˇ´ıva´me je paralelneˇ. • Distribuovane´ vy´pocˇty (vıće spolupracujıćıćh gramatik) • Dalsˇ´ı.

77

KAPITOLA 6 FORMA´LNI´ SYSTE´MY

6.2

78

Gramatiky pouzˇ´ıvajıćı´ rˇ´ızenou sekvencˇnı´ derivaci

Existuje neˇkolik typu˚ gramatik, ktere´ sice pouzˇ´ıvajı´ sekvencˇnı´ postup derivovańı´, ale za´rovenˇ tento postup rˇ´ıdı´ (kdy, prˇ´ıpadneˇ kde se ktere´ pravidlo pouzˇije). Jsou to naprˇ´ıklad maticove´ gramatiky. Maticova´ gramatika je rozsˇ´ırˇenı´m bezkontextove´ gramatiky z Chomske´ho hierarchie. Mnozˇinu pravidel nahrazujeme mnozˇinou posloupnostı´, kterou nazy´va´me matice. Jsou to posloupnosti pravidel s pevneˇ dany´m porˇadı´m (obdoba tabulek u T0L-syste´mu˚, azˇ na pevne´ porˇadı´). Derivace probı´ha´ tak, zˇe si v matici vybereme posloupnost, kterou v dane´m kroku pouzˇijeme, a pravidla v posloupnosti uplatnˇujeme v porˇadı´ zleva doprava. Musı´me pouzˇ´ıt vsˇechna pravidla posloupnosti (a to pra´veˇ jednou), v dane´m porˇadı´. Definice 6.1 (Maticova´ gramatika) Maticova´ gramatika je usporˇa´dana´ cˇtverˇice GM , GM = (N, T, M, S), M = {m1 , m2 , . . . , mk }, kde M je matice k posloupnostı´ pravidel.

✍

Krok odvozenı´ ⇒M probı´ha´ takto: • vybereme si neˇkterou posloupnost pravidel mi ∈ M, • na prˇepisovany´ rˇeteˇzec pouzˇijeme prvnı´ pravidlo z mi , • pouzˇijeme druhe´ pravidlo z mi (to mu˚zˇe zpracovat i symboly vygenerovane´ prvnı´m pravidlem z mi ), • pouzˇijeme trˇetı´ pravidlo z mi , atd. Prˇı´klad 6.1 GM = ({S, A, B, C, D}, {a, b}, {m1 , m2 , m3 , m4 }, S), kde m1 m2 m3 m4

= (S → ABCD), = (A → aA, B → B, C → aC, D → D), = (A → A, B → bB, C → C, D → bD), = (A → a, B → b, C → a, D → b) Uka´zka odvozenı´:

S ⇒M ABCD ⇒M aABaCD ⇒M aAbBaCbD ⇒M aAbbBaCbbD ⇒M aabbbaabbb V derivaci jsme pouzˇili nejdrˇ´ıv prvnı´ matici, pak druhou, dvakra´t za sebou trˇetı´ a nakonec cˇtvrtou, ktera´ ukoncˇila derivaci. Generovany´ jazyk nenı´ bezkontextovy´: L(GM ) = L23 = {ai bj ai bj | i, j ≥ 1}


79


80

Prˇı´klad 6.2 GM = ({S, A, B, C}, {a, b, c}, {m1 , m2 , m3 }, S), kde m1 = (S → ABC), m2 = (A → aA, B → bB, C → cC), m3 = (A → a, B → b, C → c)

Uka´zka odvozenı´: S ⇒M ABC ⇒M aAbBcC ⇒M aaAbbBccC ⇒M aaabbbccc Generovany´ jazyk je L19 = {an bn cn | n ≥ 1}

✎

Veˇta 6.1 Maticove´ gramatiky jsou silneˇjsˇ´ı nezˇ bezkontextove´: L (CF ) ⊂ L (M AT )

(6.1)

Du˚kaz: Pro kteroukoliv bezkontextovou gramatiku sestrojı´me maticovou gramatiku, ktera´ by generovala tenty´zˇ jazyk, velmi jednodusˇe – pro kazˇde´ pravidlo bezkontextove´ gramatiky vytvorˇ´ıme samostatnou (tedy jednoprvkovou) posloupnost, matice tedy bude obsahovat tolik posloupnostı´, kolik meˇla pu˚vodnı´ gramatika pravidel. Takto vytvorˇena´ maticova´ gramatika prˇesneˇ kopı´ruje sekvencˇnı´ postup odvozovańı´ pu˚vodnı´ bezkontextove´ gramatiky. Vlastnı´ podmnozˇina je zrˇejma´: L19 = {an bn cn | n ≥ 1} ∈ L (M AT ) − L (CF ) (je generovań maticovou gramatikou v prˇ´ıkladu 6.2). 2

6.3

Gramaticke´ syste´my

Dosud uvedene´ modely pocˇ´ıtajı´ s jedinou gramatikou vybavenou (vy´vojovy´mi) pravidly, a s jediny´m slovem, ktere´ je zpracova´vańo pravidly gramatiky. Toto slovo mu˚zˇeme povazˇovat za prostrˇedı´, do ktere´ho gramatika zasahuje svy´mi pravidly. Tento jednoduchy´ model lze rozsˇ´ırˇit na gramaticky´ syste´m bud’ tak, zˇe pouzˇijeme neˇkolik gramatik, ktere´ majı´ kazˇda´ vlastnı´ prostrˇedı´ a mezi nimi probı´ha´ urcˇita´ komunikace, a nebo tyto gramatiky necha´me spolupracovat na spolecˇne´m prostrˇedı´ a prˇ´ıpadneˇ prˇida´me neˇktere´ dalsˇ´ı vlastnosti. Komunikace pak mu˚zˇe probı´hat

"


81

trˇeba prˇes prostrˇedı´. Cˇinnost teˇchto gramatik by´va´ synchronizovańa univerza´lnı´mi hodinami. Prvnı´ modely gramatickyćh syste´mu˚ se objevily uzˇ v roce 1978 a byly motivovańy vyuzˇitı´m v distribuovane´ umeˇle´ inteligenci. Sˇlo o tzv. spolupracujıćı´ (cooperating) gramatiky. Veˇtsˇ´ıch mozˇnostı´ vyuzˇitı´ se docˇkaly tzv. CD (Cooperated Distributed) gramaticke´ syste´my, ktere´ pracovaly metodou dnes naprˇ´ıklad v socia´lnıćh veˇdaćh oznacˇovanou jako cˇerna´ tabule (blackboard architecture for problem solving) – spolecˇne´ prostrˇedı´ je jakousi tabulı´, na kterou se „dı´vajı´ “ gramatiky a sledujı´, zda se na te´to tabuli neobjevı´ neˇco, co doka´zˇou zpracovat svy´mi pravidly. Podobne´ modely majı´ sve´ prakticke´ vyuzˇitı´ naprˇ´ıklad v robotice nebo prˇi programovańı´ neza´vislyćh softwarovyćh agentu˚. Gramaticky´m syste´mem modelujeme chovańı´ robotu˚ cˇi agentu˚ (prˇedstavovanyćh gramatikami, pravidla jsou mnozˇina proveditelnyćh akcı´) pohybujıćıćh se ve spolecˇne´m prostrˇedı´, at’ uzˇ softwarove´m (operacˇnı´ syste´m cˇi pocˇ´ıtacˇova´ sı´t’) nebo fyzicky rea´lne´m (mı´stnost). V takove´m prˇ´ıpadeˇ neˇkdy hovorˇ´ıme o agentovyćh syste´mech.

6.3.1 Kolonie Kolonie jsou velmi jednoduchy´ gramaticky´ syste´m, ktery´ mu˚zˇeme cha´pat jako spolecˇenstvı´ jednoduchyćh gramatik – komponent, ktere´ spolupracujı´ na sdı´lene´m prostrˇedı´. Vsˇechny gramatiky sdruzˇene´ v kolonii majı´ spolecˇnou abecedu a termina´lnı´ abecedu. Abeceda kolonie je mnozˇina symbolu˚, ktere´ se mohou vyskytovat v prostrˇedı´ a se ktery´mi tedy lze pracovat, termina´lnı´ abeceda (je podmnozˇinou abecedy kolonie) urcˇuje symboly, ze kteryćh se mohou skla´dat termina´lnı´ slova, ktera´ pak rˇadı´me do jazyka kolonie. Kazˇda´ komponenta ma´ svu˚j startovacı´ symbol a jazyk. Startovacı´ symbol je neˇktery´ prvek abecedy kolonie (mu˚zˇe patrˇit i do termina´lnı´ abecedy syste´mu), urcˇuje „objekt“, se ktery´m komponenta doka´zˇe pracovat. Jazyk komponenty je mnozˇina slov nad abecedou kolonie neobsahujıćıćh startovacı´ symbol komponenty, je to jaka´si mnozˇina „akcı´“, ktere´ komponenta mu˚zˇe s neˇktery´m vy´skytem sve´ho startovacı´ho symbolu v prostrˇedı´ prove´st. Cˇinnost komponenty mu˚zˇeme tedy cha´pat tak, zˇe hleda´ v prostrˇedı´ svu˚j startovacı´ symbol, a pokud najde ktery´koliv jeho vy´skyt (prˇ´ıpadneˇ nezabrany´ jinou


82

komponentou, pokud komponenty pracujı´ paralelneˇ), nahradı´ ho neˇktery´m slovem sve´ho jazyka. Komponenta sama o sobeˇ je vlastneˇ jednoducha´ gramatika generujıćı´ konecˇny´ jazyk (konecˇny´ proto, zˇe startovacı´ symbol komponenty se nesmı´ vyskytovat v jejı´m jazyce), lze ji prˇepsat na regula´rnı´ gramatiku tak, zˇe na levou stranu pravidel da´me startovacı´ symbol komponenty a na pravou postupneˇ vsˇechna slova jejı´ho jazyka. Prostrˇedı´ je zpracova´vańo pouze komponentami. Mu˚zˇe obsahovat jaky´koliv rˇeteˇzec symbolu˚ patrˇ´ıcıćh do abecedy kolonie. Tento rˇeteˇzec nazy´va´me stavem prostrˇedı´, pocˇa´tecˇnı´m stavem prostrˇedı´ je axiom kolonie. Definice 6.2 (Kolonie) Kolonie je usporˇa´dana´ cˇtverˇice C = (V, T, R, ω0 ), kde • V je konecˇna´ nepra´zdna´ abeceda kolonie, • T nepra´zdna´ termina´lnı´ abeceda kolonie, T ⊆ V, • R je konecˇna´ multimnozˇina1 komponent, R = {(S, F ) | S ∈ V ), F ⊆ (V − {S})∗ , F je konecˇna´ a nepra´zdna´}, S je startovacı´ symbol komponenty (S, F ) a F je konecˇny´ jazyk te´to komponenty, • ω0 je axiom. Pro kolonie existuje hodneˇ typu˚ odvozenı´, k za´kladnı´m rˇadı´me tyto cˇtyrˇi: • sekvencˇnı´ mo´d (b, basic) – kolonie pracuje podobneˇ jako gramatiky Chomske´ho hierarchie, tedy v kazˇde´m kroku odvozenı´ je na´hodneˇ vybrańa jedna komponenta, ktera´ v prostrˇedı´ zpracuje jediny´ vy´skyt sve´ho startovacı´ho symbolu (nahradı´ ho neˇktery´m slovem sve´ho jazyka), • sekvencˇneˇ-paralelnı´ mo´d (t, terminal) – v kazˇde´m kroku odvozenı´ je sekvencˇneˇ vybrańa jedina´ komponenta, ta pak zpracuje vsˇechny vy´skyty sve´ho startovacı´ho symbolu v prostrˇedı´, kazˇdy´ z nich nahradı´ neˇktery´m ze slov sve´ho jazyka (obecneˇ kazˇdy´ vy´skyt sve´ho startovacı´ho symbolu mu˚zˇe nahradit jiny´m slovem), • slaby´ paralelismus (wp, weakly parallel) – kazˇda´ komponenta, ktera´ mu˚zˇe pracovat, take´ musı´ pracovat, tedy kdyzˇ se v dane´m kroku odvozenı´ v prostrˇedı´ 1

Pro prˇipomenutı´: v multimnozˇineˇ se narozdı´l od mnozˇiny mu˚zˇe vyskytovat i vıće stejnyćh prvku˚, tedy v multimnozˇineˇ komponent mu˚zˇe existovat i vıće komponent stejneˇ definovanyćh.


83

vyskytne startovacı´ symbol komponenty a nenı´ zpracova´vań jinou komponentou, komponenta tento symbol musı´ zpracovat, • silny´ paralelismus (sp, strongly parallel) – podobneˇ jako slaby´ paralelismus, jen navıć v prˇ´ıpadeˇ, zˇe komponenta by meˇla pracovat (jejı´ startovacı´ symbol se vyskytuje v prostrˇedı´), ale vsˇechny vy´skyty jejı´ho startovacı´ho symbolu zabraly jine´ komponenty (se stejny´m startovacı´m symbolem), je derivace zablokovańa, odvozovańı´ koncˇ´ı. Prˇı´klad 6.3 C = ({A, B, a}, {a}, R, A), kde R = {(A, {BB}), (A, {a}), (B, {A})}

Uka´zky derivacı´ s pouzˇitı´m b a t mo´du odvozenı´: A ⇒b BB ⇒b AB ⇒b aB ⇒b aA ⇒b aBB ⇒b aBA ⇒b . . . A ⇒t B 2 ⇒t A2 ⇒t B 4 ⇒t A4 ⇒t B 8 ⇒t A8 ⇒t a8 S pouzˇitı´m mo´du˚ odvozenı´ b a t jsou generovańy tyto jazyky: L(C, b) = {an | n n > 0} o 2n L(C, t) = L4 = a n ≥ 0 (take´ u 0L-syste´mu v prˇ´ıkladu 5.1 na straneˇ 67). Veˇta 6.2 Sekvencˇnı´ kolonie jsou ve sve´ generativnı´ sı´le stejneˇ silne´ jako bezkontextove´ jazyky: L (CF ) ' L (COLb ) (6.2) Du˚kaz: Podle bezkontextove´ gramatiky G = (N, T, P, S) vytvorˇ´ıme kolonii s b mo´dem odvozenı´ C = (V, T, R, ω0 ) jednodusˇe takto: • odstranı´me prˇ´ımou rekurzi (pravidla, kde na prave´ straneˇ je netermina´l z leve´ strany A → αAβ, prˇepı´sˇeme na dvojici pravidel A → A0 , A0 → αAβ), symboly A0 jsou noveˇ prˇidane´, • pravidla se stejnou levou stranou shrneme vzˇdy do jedne´ komponenty (tj. budeme mı´t tolik komponent, kolik netermina´lu˚), • V = N ∪ T ∪ {A0 | A ∈ N }, • ω0 = S, o n 0 • R = {(A, {A }) | A ∈ N } ∪ (A , {α | (A → α) ∈ P }) A ∈ N . 0

✎ "


84

Odvozenı´ bude probı´hat prakticky stejneˇ jako v bezkontextove´ gramatice, azˇ na mezikroky provedene´ pro odstraneˇnı´ rekurze. Opacˇny´ postup vyzˇaduje oddeˇlenı´ termina´lu˚ od symbolu˚, ktere´ lze prˇepisovat. Z kolonie C = (V, T, R, ω0 ) vytvorˇ´ıme bezkontextovou gramatiku G = (N, T, P, S) takto: • pro kazˇdy´ symbol termina´lnı´ abecedy a ∈ T vytvorˇ´ıme novy´ (noveˇ prˇidany´) netermina´l Na , • v gramatice budou pravidla Na → a pro kazˇdy´ symbol a ∈ T , • pravidla gramatiky vytvorˇ´ıme z komponent tak, zˇe v jazyce komponenty vsˇechny termina´ly a nahradı´me novy´mi netermina´ly Na , oznacˇme α rˇeteˇzec, ktery´ vznikl z rˇeteˇzce α tı´mto nahrazenı´m, • N = V − T ∪ {Na | a ∈ T } ∪ {S}, S ∈ / V, n o • P = {Na → a | a ∈ T } ∪ A → f1 | f2 | . . . (A, {f1 , f2 , . . .}) ∈ R ∪ {S → ω0 } 2

✎

Veˇta 6.3 Sekvencˇneˇ-paralelnı´ kolonie jsou silneˇjsˇ´ı nezˇ bezkontextove´ jazyky: L (CF ) ⊂ L (COLt )

(6.3)

Du˚kaz: Podle bezkontextove´ gramatiky G = (N, T, P, S) vytvorˇ´ıme kolonii s t mo´dem odvozenı´ C = (V, T, R, ω0 ) jednodusˇe takto: • stejneˇ jako v prˇedchozı´m du˚kazu odstranı´me prˇ´ımou rekurzi (pravidla, kde na prave´ straneˇ je netermina´l z leve´ strany A → αAβ, prˇepı´sˇeme na dvojici pravidel A → A0 , A0 → αAβ), symboly A0 jsou noveˇ prˇidane´, • pravidla se stejnou levou stranou shrneme vzˇdy do jedne´ komponenty (tj. budeme mı´t tolik komponent, kolik netermina´lu˚), • V = N ∪ T ∪ {A0 | A ∈ N }, • ω0 = S, n o • R = {(A, {A0 }) | A ∈ N } ∪ (A0 , {A} ∪ {α | (A → α) ∈ P }) A ∈ N .

"


85

Rozdı´l oproti prˇedchozı´mu du˚kazu je v definici mnozˇiny R, kde musı´me zajistit mozˇnost simulace sekvencˇnı´ho odvozenı´. Zatı´mco prˇi pouzˇitı´ t mo´du odvozenı´ v kolonii se v jednom kroku odvozenı´ prˇepisujı´ vsˇechny symboly, zde musı´ by´t mozˇnost prˇepsat jakoby jen jeden vy´skyt symbolu A a ostatnı´ nechat bez prˇepsańı´ (v simulaci na jeden vy´skyt symbolu A pouzˇijeme dotycˇne´ pravidlo, na ostatnı´ pouzˇijeme prˇepis na A prˇes A0 ). n o 2n Vlastnı´ podmnozˇinu lze doka´zat naprˇ´ıklad jazykem L4 = a n ≥ 0 generovany´m koloniı´ s t mo´dem odvozenı´ v prˇ´ıkladu 6.3 na straneˇ 83. Tento jazyk nenı´ bezkontextovy´, cozˇ se da´ doka´zat naprˇ´ıklad pomocı´ Pumping lemma. 2 Prˇı´klad 6.4 C = ({M, N, P, a, b}, {a, b}, R, M M ), kde mnozˇina R obsahuje komponenty (M, {P P N P, P N P P, ε}), (N, {M }),

(P, {a}), (P, {b})

Uka´zky derivace s pouzˇitı´m wp a sp mo´du odvozenı´: MM MM MM MM

⇒wp P P N P M ⇒wp baM P ⇒wp baa ⇒wp P P N P M ⇒wp aP M b ⇒wp aaP N P P b ⇒wp aaaM P bb ⇒wp aaabbb ⇒sp P P N P M ⇒sp P aM b odvozenı´ je zablokovańo ⇒sp P P N P M ⇒sp abM P P N P P ⇒sp abbaM P P ⇒sp abbaab

S pouzˇitı´m mo´du˚ odvozenı´ wp a sp jsou generovańy tyto jazyky: o n ∗ L(C, wp) = L24 = w ∈ {a, b} |w|a − |w|b ≤ 1, |w| = 3n, n ≥ 0 n o L(C, sp) = L25 = w ∈ {a, b}∗ |w|a = |w|b , |w| = 6n, n ≥ 0 − {ai bi , bi ai | i ≥ 1} V prˇ´ıkladu 6.4 vidı´me u sp mo´du vyuzˇitı´ blokovańı´ odvozenı´ v prˇ´ıpadeˇ, zˇe v prostrˇedı´ je pra´veˇ jeden symbol P , prˇicˇemzˇ ma´me dveˇ komponenty s tı´mto startovacı´m symbolem. Zde je blokovańı´ vyuzˇito pro zajisˇteˇnı´ stejne´ho pocˇtu symbolu˚ a a b v generovane´m sloveˇ. Kolonie s wp a sp mo´dem odvozenı´ jsou silneˇjsˇ´ı nezˇ bezkontextove´ jazyky, du˚kaz by byl stejny´ jako u du˚kazu veˇty 6.2 na straneˇ 83. Na prˇ´ıkladu 6.5 vidı´me vyuzˇitı´ blokovańı´ odvozenı´ neˇkteryćh slov, zde pouzˇito k synchronizovańı´ generovańı´ obou stejnyćh polovin slova.


86

Prˇı´klad 6.5 C = ({P, A, B, a, b}, {a, b}, R, P P ), v mnozˇineˇ R jsou komponenty (P, {aA, bB, ε}), (A, {P }), (B, {P }), (P, {aA, bB, ε}), (A, {P }), (B, {P })

Uka´zka derivace s pouzˇitı´m sp (silneˇ paralelnı´ho) mo´du odvozenı´: P P ⇒sp aAaA ⇒sp aP aP ⇒sp aaAaaA ⇒sp aaP aaP ⇒sp aabBaabB ⇒sp ⇒sp aabP aabP ⇒sp aabaab Tato kolonie s sp mo´dem odvozenı´ generuje jazyk L(C, wp) = L5 = {ww | w ∈ {a, b}∗ } S wp mo´dem odvozenı´ bychom vygenerovali jazyk {a, b}∗ .

Jistou mozˇnost blokovańı´ neˇkteryćh odvozenı´ vsˇak lze pouzˇ´ıt i u wp mo´du odvozenı´ (nekonecˇny´m cyklem), jak vidı´me na prˇ´ıkladu 6.6. Prˇı´klad 6.6 C = ({P, Q, R, X, Y, B, B 0 , a, b}, {a, b}, R, P P ), v mnozˇineˇ R jsou komponenty (P, {aQX, bRX, Y }), (P, {aRY, bQY, X}),

(Q, {P }), (Q, {B}),

(R, {P }), (R, {B}),

(X, {ε}), (X, {B}),

(Y, {ε}), (Y, {B}),

0

(B, {B }), (B 0 , {B})

Uka´zka derivacı´ s pouzˇitı´m wp (slabeˇ paralelnı´ho) mo´du odvozenı´: P P ⇒wp aQXaRY ⇒wp aP aP ⇒wp abRXabQY ⇒wp abP abP ⇒wp abXabY ⇒wp ⇒wp abab P P ⇒wp aQXbQY ⇒wp aP bB ⇒wp aY bB 0 ⇒wp abB ⇒wp abB 0 ⇒wp . . . S pouzˇitı´m mo´du odvozenı´ wp je generovań jazyk L5 . Kdybychom zde pouzˇili prˇi odvozovańı´ sp mo´d, zı´skali bychom pra´zdny´ jazyk.

Seznam pouzˇityćh jazyku˚

L1 = {an bn | n ≥ 1} » » » » »

prˇ´ıklad 1.1, Pumping lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . prˇ´ıklad 1.6, Parikhu˚v vektor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . prˇ´ıklad 1.9, Parikhu˚v vektor a reg. jazyky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . prˇ´ıklad 1.11, Dycku˚v jazyk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . du˚kaz veˇty 5.6, ∈ / L (T 0L) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6 9 11 13 73

L2 = {an bn cn | n ≥ 0} » » » » » »

prˇ´ıklad 1.2, ∈ / L (CF ), Pumping lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . prˇ´ıklad 1.13, ∈ / L (CF ), Dycku˚v jazyk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . du˚kaz veˇty 1.13, ∈ / L (CF ), Pru˚nik jazyku˚ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . prˇ´ıklad 3.2, Za´sobnı´kovy´ automat se dveˇma za´sobnı´ky . . . . . . . . . . . . . . . . prˇ´ıklad 3.4, Turingu˚v stroj . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . prˇ´ıklad 5.7, ∈ L (ET 0L), ET0L-syste´m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

n o n2 L3 = a n ≥ 0

» »

prˇ´ıklad 1.3, ∈ / L (CF ), Pumping lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . prˇ´ıklad 1.19, bezkontextova´ substituce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

n o n L 4 = a2 n ≥ 0

» » »

prˇ´ıklad 1.4, ∈ / L (CF ), Pumping lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . prˇ´ıklad 5.1, ∈ L (0L), 0L-syste´m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . prˇ´ıklad 6.3, ∈ L (COLt ), kolonie s t mo´dem odvozenı´ . . . . . . . . . . . . . . . . . .

87

7 14 18 43 46 74

7 20

8 67 83

SEZNAM POUZˇITYĆH JAZYKU˚

88

L5 = {ww | w ∈ {a, b}∗ } » » » »

prˇ´ıklad 1.5, ∈ / L (CF ), Pumping lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . prˇ´ıklad 4.1, ∈ L (1), nezkracujıćı´ gramagika . . . . . . . . . . . . . . . . . . . . . . . . . . . prˇ´ıklad 6.5, ∈ L (COLsp ), kolonie s sp mo´dem odvozenı´ . . . . . . . . . . . . . . . prˇ´ıklad 6.6, ∈ L (COLwp ), kolonie s wp mo´dem odvozenı´ . . . . . . . . . . . . . .

8 57 86 86

L6 = {an bm an | 0 ≤ m ≤ n} »

v pozna´mce ∈ / L (CF ), Pumping lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

L7 = {a3n bn+2 a4 cn | n ≥ 1} » »

prˇ´ıklad 1.6, Parikhu˚v vektor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . prˇ´ıklad 1.9, Parikhu˚v vektor a reg. jazyky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9 11

L8 = {a2n bn−1 | n ≥ 1} » »

prˇ´ıklad 1.6, Parikhu˚v vektor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . prˇ´ıklad 1.12, Dycku˚v jazyk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9 14

L9 = {ai bj ck | i, j, k ≥ 1, i = j nebo j = k} » » » »

prˇ´ıklad 1.7, Parikhu˚v vektor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . prˇ´ıklad 1.14, sjednocenı´ jazyku˚ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . prˇ´ıklad 1.16, uzavrˇenost vzhledem k zrcadlenı´ . . . . . . . . . . . . . . . . . . . . . . . . . prˇ´ıklad 1.17, substituce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

10 15 17 18

L10 = {a∗ bc} ∪ {ap ban c | n ≥ 0, p je prvocˇ´ıslo} »

prˇ´ıklad 1.8, ∈ / L (CF ), Parikhu˚v vektor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

n o 2 L11 = an bn | n ≥ 1 »

L12 »

prˇ´ıklad 1.8, ∈ / L (CF ), Parikhu˚v vektor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

n o n2 n = a b |1≤n≤8

Parikhu˚v vektor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11

11

11

L13 = {an1 bn1 an2 bn2 . . . ank bnk | k ≥ 0, ni ≥ 1, 1 ≤ i ≤ k} »

prˇ´ıklad 1.18, ∈ L (CF ), uza´veˇrove´ vlastnosti . . . . . . . . . . . . . . . . . . . . . . . . . . .

19

SEZNAM POUZˇITYĆH JAZYKU˚ L14 = wcwR | w ∈ {a, b}∗

» » »

prˇ´ıklad 2.1, ∈ L (ZA), za´sobnı´kovy´ automat . . . . . . . . . . . . . . . . . . . . . . . . . . . prˇ´ıklad 2.2, za´sobnı´kovy´ automat – stavovy´ diagram . . . . . . . . . . . . . . . . . . prˇ´ıklad 2.3, prˇevod gramatiky na za´sobnı´kovy´ automat . . . . . . . . . . . . . . . .

L15 = an cbn ck | n ≥ 0, k > 0 » »

prˇ´ıklad 2.4, jednostavovy´ za´sobnı´kovy´ automat . . . . . . . . . . . . . . . . . . . . . . . . prˇ´ıklad 2.5, prˇevod za´sobnı´kove´ho automatu na gramatiku . . . . . . . . . . . .

L16 = wwR | w ∈ {a, b}∗

» »

prˇ´ıklad 2.6, ∈ L (CF ), pru˚nik s reg. jazykem . . . . . . . . . . . . . . . . . . . . . . . . . . . du˚kaz veˇty 2.9, ∈ / L (DZA), deterministicke´ bezkontextove´ jazyky . . . . .

89

24 25 29

31 33

36 37

L17 = {an an | n ≥ 0} = {a2n | n ≥ 0} » L18 »

prˇ´ıklad 2.6, ∈ L (CF ), pru˚nik CF a REG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . n o ∗ = w ∈ {a, b, c} |w|a = |w|b = |w|c

prˇ´ıklad 2.7, ∈ / L (CF ), pru˚nik CF a REG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

36

37

L19 = L2 − {ε} = {an bn cn | n ≥ 1} » » »

prˇ´ıklad 3.5, prˇevod gramatiky na Turingu˚v stroj . . . . . . . . . . . . . . . . . . . . . . . prˇ´ıklad 5.4, ∈ L (E0L), E0L-syste´m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . prˇ´ıklad 6.2, ∈ L (M AT ), maticova´ gramatika . . . . . . . . . . . . . . . . . . . . . . . . . .

49 70 80

n

L20 = {a3·2 | n ≥ 1} »

prˇ´ıklad 5.2, ∈ L (0L), 0L-syste´m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

68

L21 = {a, aa} » »

du˚kaz veˇty 5.1, ∈ / L (0L) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . prˇ´ıklad 5.5, ∈ L (E0L), E0L-syste´m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

n o n L22 = L4 ∪ {ε} = a2 n ≥ 0 ∪ {ε}

» »

prˇ´ıklad 5.6, ∈ L (T 0L), T0L-syste´m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . du˚kaz veˇty 5.5, ∈ / L (0L) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

68 71

72 73

SEZNAM POUZˇITYĆH JAZYKU˚

90

L23 = {ai bj ai bj | i, j ≥ 1} »

prˇ´ıklad 6.1, ∈ L (M AT ), maticova´ gramatika . . . . . . . . . . . . . . . . . . . . . . . . . .

o n L24 = w ∈ {a, b}∗ |w|a − |w|b ≤ 1, |w| = 3n, n ≥ 0

»

L25 »

prˇ´ıklad 6.4, ∈ L (COLwp ), kolonie s wp mo´dem odvozenı´ . . . . . . . . . . . . . .

n o ∗ = w ∈ {a, b} |w|a = |w|b , |w| = 6n, n ≥ 0 − {ai bi , bi ai | i ≥ 1}

prˇ´ıklad 6.4, ∈ L (COLsp ), kolonie s sp mo´dem odvozenı´ . . . . . . . . . . . . . . .

78

85

85

TEORIE JAZYKŮ A AUTOMATŮ II

Recommend Documents