Vysoke ucen technicke v Brne Fakulta informa cn ch technologi
Projekt v r amci p redm etu TJD
Formaln modely jazyk u zalozene na automatech a jejich modi kace
2005
Radek Bidlo
Abstrakt
Tento dokument popisuje zakladn modely formalnch jazyku zalozene na automatech a zavad nektere dals modi kace, kterymi je mozne zvysit jejich akceptacn schopnosti. Detailneji je pojednano o oboustrannych zasobnkovych automatech nad volnou grupou, ktere vychaz z klasickych zasobnkovych automatu. Na zaver je prezentovan dukaz ekvivalence trdy jazyku prijmanych temito automaty s trdou rekurzvne vycslitelnych jazyku.
Obsah 1 Uvod
4
2 Zakladn pojmy a de nice
5
3 Konecne a zasobnkove automaty
7
4 Konecne automaty nad grupami
9
2.1 2.2 2.3 2.4
Symbol, abeceda, retezec . . . . . . . . . . . . . . . . . . . . . . . Jazyk nad abecedou . . . . . . . . . . . . . . . . . . . . . . . . . Chomskeho hierarchie jazyku . . . . . . . . . . . . . . . . . . . . Grupy a volne grupy . . . . . . . . . . . . . . . . . . . . . . . . .
3.1 Konecne automaty . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Zasobnkove automaty . . . . . . . . . . . . . . . . . . . . . . . .
5 5 5 6
7 8
4.1 Nova charakterizace bezkontextovych jazyku . . . . . . . . . . . 9 4.2 Diskuse ke konecnym automatum . . . . . . . . . . . . . . . . . . 11
5 Oboustranne zasobnkove automaty nad volnymi grupami
12
6 Zaver
20
5.1 Frontove gramatiky . . . . . . . . . . . . . . . . . . . . . . . . . . 12 5.2 Oboustranne zasobnkove automaty nad volnymi grupami . . . . 13 5.3 Diskuse k zasobnkovym automatum . . . . . . . . . . . . . . . . 19
1 Uvod
Automaty predstavuj zakladn formaln model jakehokoliv vypoctu. Ten je zpravidla reprezentovan urcitou posloupnost prechodu konkretnho automatu mezi jednotlivymi jeho kon guracemi podle presne danych pravidel, ktere jsou soucast de nice automatu. Vypocet pak muzeme prohlasit za uspesny, nachaz-li se automat po proveden poslednho vypocetnho kroku v kon guraci, ktera je de novana jako clova. V opacnem prpade je vypocet neuspesny. Clova kon gurace byva zpravidla reprezentovana koncovym stavem automatu, ale mohou pribyt i dals podmnky jako je naprklad vyprazdnen zasobnku a podobne. Samozrejmost je kompletn nacten vstupnho retezce. Z hlediska teorie formalnch jazyku chapeme automaty jako tzv. akceptory jazyk u. Jazyk prijmany danym automatem pak zpravidla de nujeme jako mnozinu vsech vet, ktere je schopen automat zpracovat a pritom po proveden poslednho kroku skoncit v nektere z clovych kon gurac. Posloupnost takovychto kroku vedoucch do nektere clove kon gurace pri prijman urciteho retezce je pak mozno chapat jako uspesny vypocet daneho automatu. Nejznamejs z automatu, ktere se behem vyvoje teoreticke informatiky ustalily jako jakesi zakladn verze, jsou zejmena konecne automaty, zasobnkove automaty a Turingovy stroje. My se budeme podrobneji zabyvat konecnymi a zasobnkovymi automaty. V nasledujcch kapitolach si uvedeme vzdy presnou de nici a ukazeme, jakou trdu jazyku jsou schopny ve sve zakladn variante de novat. Dale zavedeme nektera jejich rozsren prpadne omezen a budeme studovat akceptacn schopnosti nove vzniklych modelu. Podrobne se zamerme zejmena na automaty zasobnkove. U ctenare se predpoklada zakladn znalost teorie formalnch jazyku a algebry, viz [1] a [2].
4
2 Zakladn pojmy a de nice
V teto kapitole zopakujeme naproste zaklady teorie formalnch jazyku a de nujeme si formalne pojmy jako jsou abeceda, retezec, a jazyk nad abecedou. Zakladn de nice jsou prevzaty z [3]. 2.1
Symbol, abeceda, ret ezec
De nice 2.1 Abecedou nazveme kazdou konecnou neprazdnou mnozinu prvku,
ktere nazavame symboly teto abecedy. Libovolna sekvence symbolu urcite abecedy tvor retezec. Oznacme-li symbolem " prazdny retezec, tedy retezec, ktery neobsahuje zadne symboly, muzeme vsechny retezce de novat rekurzvne. Necht' je libovolna abeceda. 1. " je retezec nad 2. je-li x retezec nad a a 2 , pak take xa je retezec nad
De nice 2.2
2.2
Jazyk nad abecedou
Uvazujme libovolnou abecedu . Oznacme mnozinu vsech retezcu nad abecedou vcetne retezce prazdneho a + mnozinu vsech retezcu nad abecedou vyjma retezce prazdneho, tedy + = f"g. Jinymi slovy, + obsahuje vsechny neprazdne retezce nad abecedou . resp. + se nazyva iterace resp. pozitivn iterace mnoziny . De nujme nyn jazyk nad abecedou . De nice 2.3
Necht' je abeceda a necht' L . Potom L je jazyk nad
abecedou . Z teto de nice je zrejme, ze jazykem nad urcitou abecedou muze byt vlastne libovolna podmnozina iterace teto mnoziny. Otazkou zustava, jak takovy jazyk popsat. Moznost je nekolik. Jedna z nejmene praktickych je prmy vycet prvku jazyka. Tato varianta je vsak zcela nepouzitelna v prpade nekonecnych jazyku a problemy nastavaj jiz pri pokusu o popis rozsahlych konecnych jazyku. Proto byly vyvinuty urcite formaln modely, ktere poskytuj konecne prostredky pro popis obecne nekonecnych jazyku. Tyto modely muzeme rozdelit do dvou zakladnch skupin | gramatiky a automaty. My se v tomto projektu zamerme prave na automaty. 2.3
Chomsk eho hierarchie jazyk u
V roce 1956 rozdelil americky jazykovedec Avram Noam Chomsky jazyky do hierarchie podle tvaru prepisovacch pravidel gramatik, kterymi mohou byt generovany. Tato hierarchie byla jednm z nejvyznamnejsch objevu dvacateho stolet v oblasti teorie formalnch jazyku a dosud nese jeho jmeno. Prestoze se postupem casu objevily dals formaln modely, ktere svymi vyjadrovacmi schopnostmi 5
zasahuj pres nekolik trd jazyku Chomskeho hierarchie (tedy jsou schopny popsat z kazde skupiny pouze nektere jazyky), jedna se stale o jedno ze zakladnch clenen jazyku a trdy jazyku teto hierarchie byvaj srovnavany v mnoha dukazech ekvivalence trd jazyku de novanych jinymi formalnmi modely. Protoze je tento dokument zameren hlavne na automaty jako prostredky pro popis formalnch jazyku, popisme si jednotlive trdy jazyku Chomskeho hierarchie pouze neformalne. jazyky typu 0 | zahrnuj vsechny jazyky s gramatickym zakladem; vsechny tyto jazyky jsou prijmany Turingovymi stroji a jsou zname taktez pod oznacenm rekurzvne vycslitelne jazyky jazyky typu 1 | zname tez pod oznacenm kontextove jazyky ; vsechny tyto jazyky jsou prijmany linearne ohranicenymi nedeterministickymi Turingovymi stroji jazyky typu 2 | oznacovany tez jako bezkontextove jazyky ; tyto jazyky jsou prijmany nedeterministickymi zasobnkovymi automaty (viz dale) a predstavuj urcity teoreticky zaklad syntaxe mnoha programovacch jazyku jazyky typu 3 | oznacovany vetsinou jako regularn jazyky, ktere jsou prijmany konecnymi automaty (viz dale) Jednotlive trdy jsou vzajemne vazany ostrou inkluz. Oznacme-li symboly RE, CS, CF a REG postupne trdu rekurzvne vycslitelnych, kontextovych, bezkontextovych a regularnch jazyku, potom plat REGCFCSRE. 2.4
Grupy a voln e grupy
V teto casti uvedeme velmi strucne de nici grupy a jej zobecnene varianty | volne grupy (zejmena s ohledem na nase dals pouzit v kapitole 5). Teorie grup tvor samostatnou algebraickou disciplnu a je velmi obsahla. My si zde proto uvedeme opravdu jen to nejdulezitejs, co budeme v dalsch castech tohoto dokumentu potrebovat. Necht' V je mnozina. Strukturu (V; ; e) nazveme grupou, jestlize : V V ! V je binarn asociativn operator (uzavreny na V ) existuje unikatn prvek e 2 V takovy, ze e a = a e = a pro kazde a 2 V pro kazde a 2 V existuje a 2 V takove, ze a a = a a = e;
De nice 2.4
Necht' V je abeceda a necht' je binarn asociativn operator konkatenace. Strukturu (V ; ; ") nazveme volnou grupou generovanou mnozinou V a operac konkatenace, jestlize pro kazde dva retezce x; y 2 V plat x y 2 V existuje unikatn retezec " zvany prazdny, ktery je neutralnm prvkem teto struktury (tj. pro kazdy retezec x 2 V plat x " = " x = x) pro kazdy retezec tvaru x = x1x2 : : : x 2 V , n 0 existuje x = x : : : x2x1 zvany inverzn takovy, ze plat x x = x x = "
De nice 2.5
n
6
n
3 Konecne a zasobnkove automaty
Automaty, chapane jako formaln modely vypoctu nebo jako akceptory jazyku, lze rozdelit do nasledujcch trd. 1. Konecne automaty 2. Zasobnkove automaty 3. Turingovy stroje My se v tomto dokumentu zamerme na konecne a zasobnkove automaty. V teto kapitole si uvedeme jejich zakladn de nici. V dals kapitole potom ukazeme, jak vhodnym rozsrenm zakladnch modelu muzeme vyrazne zvysit jejich akceptacn schopnosti. Poznamenejme, ze dale se jiz automaty nebudeme zabyvat ve smyslu modelu vypoctu, ale ve smyslu akceptoru jazyku. 3.1
Kone cn e automaty
Konecny automat je nejslabs formaln model z vyse uvedene skupiny. Jak jsme jiz uvedli vyse, konecne automaty de nuj pouze trdu regularnch jazyku. Uved'me si nyn jeho formaln de nici. je petice, M = (Q; ; R; q0; F ), kde Q je konecna mnozina vnitrnch stavu je konecna vstupn abeceda R je konecna mnozina pravidel tvaru pa ! q, kde p; q 2 Q, a 2 ; v prpade, ze plat a 2 [f"g, nazyva se konecny automat rozsreny ; pokud navc pro kazdy symbol a 2 plat, ze existuje pro kazdy stav q 2 Q nejvyse jedno pravidlo qa ! p, pro nejake p 2 Q, nazyva se takovyto konecny automat
De nice 3.1 Konecny automat
deterministicky
q0 2 Q je pocatecn stav F Q je mnozina koncovych stavu
Kon gurac konecneho
automatu M rozumme retezec qx, kde q 2 Q a x 2 . Pokud qax a px jsou dve kon gurace a qa ! p 2 R, pak automat M provad prechod z kon gurace qax do kon gurace px podle pravidla qa ! p a pseme qax ` px[qa ! p] nebo strucneji qax ` px. Symbol ` oznacuje relaci prechodu mezi jednotlivymi kon guracemi. Symboly ` , `+ a ` oznacuj postupne posloupnost prechodu delky n, n 0, tranzitivn uzaver a re exivn-tranzitivn uzaver relace prechodu `. Jazyk prijmany automatem M je de novan jako L(M ) = fwjw 2 ^ q0 w ` f ^ f 2 F g Poznamenejme na zaver tohoto odstavce, ze deterministicke konecne automaty maj stejnou vyjadrovac schopnost jako nedeterministicke, tedy de nuj rovnez trdu regularnch jazyku. C lenen z tohoto hlediska vsak pro nas nen podstatne a proto se jm nebudeme zabyvat. n
7
3.2
Z asobn kov e automaty
Zasobnkovy automat (pushdown automaton, PDA) svym zpusobem predstavuje urcite rozsren konecneho automatu v tom smyslu, ze obsahuje zasobnk jako vnejs pamet' teoreticky neomezene velikosti. Jeho generativn sla je v Chomskeho hierarchii o stupen vyse | jak jsme jiz uvedli drve, nedeterministicke zasobnkove automaty de nuj trdu bezkontextovych jazyku. Na rozdl od konecnych automatu, deterministicke zasobnkove automaty maj nizs vyjadrovac schopnost nez nedeterministicke. Oznacme-li PDA(N ED) trdu jazyku prijmanych nedeterministickymi zasobnkovymi automaty a PDA(DET ) trdu jazyku prijmanych deterministickymi zasobnkovymi automaty, pak plat REG PDA(DET ) PDA(N ED) = CF Pokud budeme v dalsch castech hovorit o zasobnkovem automatu (nebo jeho modi kaci), budeme mt vzdy na mysli nedeterministickou variantu. Uved'me si nyn formaln de nici. De nice 3.2 Zasobnkovy automat
kde
je n-tice M = (Q; ; I
PD
; R; Z; q0 ; F
),
Q je konecna mnozina stavu je konecna vstupn abeceda je konecna zasobnkova abeceda R je konecna mnozina pravidel tvaru Apa ! wq, kde A 2 , p; q 2 Q, a 2 [ f"g, and w 2 Z 2 je pocatecn symbol zasobnku q0 2 Q je pocatecn stav F Q je mnozina koncovych stavu Kon gurac zasobnkoveho automatu M rozumme retezec yqx, kde q 2 Q, y 2 a x 2 . Pokud uAqav a uwpv jsou dve kon gurace a Aqa ! wp 2 R, I
PD
PD
I
PD
PD
pak automat M provad prechod z kon gurace uAqav do kon gurace uwpv podle pravidla Aqa ! wp a pseme uAqav ` uwpv [Aqa ! wp] nebo strucneji uAqav ` uwpv. Symboly ` , `+ a ` oznacuj postupne posloupnost prechodu delky n, n 0, tranzitivn uzaver a re exivn-tranzitivn uzaver relace prechodu `. Jazyk prijmany automatem M m uze byt de novan tremi zpusoby: a) prechodem do koncoveho stavu: L(M ) = fwjw 2 ^ Zq0w ` rf; where f 2 F; r 2 g b) s vyprazdnenm zasobnku: L(M ) = fwjw 2 ^ Zq0w ` p; where p 2 Qg c) prechodem do koncoveho stavu a s vyprazdnenm zasobnku: L(M ) = fwjw 2 ^ Zq0w ` f; where f 2 F g Klasicke konecne a zasobnkove automaty jsou v teorii formalnch jazyku vseobecne zname a tvor vyznamny formaln zaklad pro nescetne mnozstv praktickych aplikac (zejmena v oblasti lexikaln a syntakticke analyzy). V dalsch castech si ale ukazeme nektere dals prostredky, jakymi muzeme schopnosti konecnych a zasobnkovych automatu vylepsit. PD
I
n
f
I
PD
e
I
fe
I
8
4 Konecne automaty nad grupami
Napln teto kapitoly je cerpana z [4] a [5]. Necht' K = (M; ; e) je grupa s bazovou mnozinou M , binarn operac a neutralnm prvkem e. (extended nite automaton, EFA) nad grupou K je sestice A = (Q; ; K; R; q0; F ), kde Q, , q0, F maj stejny vyznam jako v prpade bezneho konecneho automatu, tedy konecna mnozina stavu, konecna vstupn abeceda, pocatecn stav a mnozina koncovych stavu (v tomto porad) R : Q ( [ f"g) ! P (Q M ) Takto de novany automat muzeme povazovat za bezny konecny automat, ktery ma navc registr pro uchovan libovolneho prvku z M . Relace (q; m) 2 R(s; a), kde q; s 2 Q, a 2 [ f"g, m 2 M znamena, ze automat A zmen sv uj soucasny stav s na stav q, precte ze vstupn pasky symbol a a do registru uloz hodnotu x m, kde x je stary obsah registru. Startovac hodnota registru je e. Kon gurac takovehoto automatu rozumme trojici (q; u; m), kde q 2 Q, u 2 a m 2 M . Necht' potom (q; aw; m) a (s; w; m r) jsou dve kon gurace, r 2 M , a necht' (s; r) 2 R(q; a). Pak pseme (q; aw; m) ` (s; w; m r) a rkame, ze automat A provad krok (prechod) z kon gurace (q; aw; m) do kon gurace (s; w; m r) podle (s; r) 2 R(q; a). My se dale zamerme na rozsrene konecne automaty nad volnymi grupami. Pripomenme, ze pro kazdou (ne-abelovskou) grupu K existuje homomor smus z volne grupy do K. Volnou grupu generovanou nejakou neprazdnou spocetnou mnozinou M oznacme F(M ). Grupu s n generatory potom oznacme jako F . Dale oznacme L(EF A(F )) trdu jazyku prijmanych rozsrenymi konecnymi automaty nad volnymi grupami s n generatory. Pripomenme z [7] de nici aditivn valencn gramatiky (additive valence grammar), ktera generuje jazyk podobnym zpusobem jako je de novan jazyk prijmany vyse popsanym rozsrenym konecnym automatem. Aditivn valencn gramatika je petice, G = (N; T; P; S; v), kde (N; T; P; S ) je bezna gramatika Chomskeho hierarchie a v je zobrazen z P do mnoziny celych csel. Jazyk generovany gramatikou G je tvoren vsemi retezce nad terminaln abecedou T takovymi, ktere byly vygenerovany posloupnost pravidel p1, p2,: : :, p 2 P a zaroven v(p1) + v (p2 ) + : : : + v (p ) = 0. Protoze F1 a aditivn grupa celych csel jsou isomorfn, potom kazdy jazyk generovany nejakou regularn gramatikou s aditivn valenc je obsazen v L(EF A(F1)) a naopak. De nice 4.1 Rozsreny konecny automat
f
n
n
n
n
4.1
Nov a charakterizace bezkontextov ych jazyk u
V predchozch kapitolach jsme si jiz de novali vse potrebne pro to, abychom mohli uvest vyznamny vysledek teto kapitoly prevzaty z [5].
9
Veta 4.1 CF= L(EF A(F2 ))
Jinymi slovy tento matematicky zapis rka, ze kazdy bezkontextovy jazyk muze byt prijman rozsrenym zasobnkovym automatem nad volnou grupou se dvema generatory. Uved'me si alespon nastin dukazu teto vety, ktery bude sestavat ze dvou cast. Prvn cast dokazuje inkluzi CF L(EF A(F2)), tedy skutecnost, ze trda bezkontextovych jazyku je obsazena v trde jazyku prijmanych rozsrenymi konecnymi automaty nad volnymi grupami s dvema generatory. Proof
Necht' je bezkontextovy jazyk prijmany nejakym zasobnkovym automatem =( ) koncovym stavem a vyprazdnenm zasobnku, kde = , = . Bez ztraty obecnosti dale muzeme predpokladat, ze pro libovolny koncovy stav jiz nen de novan zadny prechod. Polozme M = fc1; c2; : : : ; c g a zaved'me zobrazen : ! F(M ) jako (X ) = c , 1 n. Nyn konstruujme rozsreny konecny automat nad volnou grupou F(M ), A = (Q [ fs0g; V; F(M ); f; s0; F ), kde f (s0 ; ") = f(q0 ; c1 )g a [ f(p; ((X )) 1(Y ) : : : (Y2)(Y1))jXqa ! Y1Y2 : : : Y p 2 Rg[ f (q; a) =
L P Q; V; ; R; Z; q0 ; F fX1; X2; : : : ; Xng X1 Z n
X
i
m
2
m
[ f(p; ((X )) 1jXqa ! p 2 Rg
X
i
2
pro vsechna a 2 V [ f"g a q 2 Q. Matematickou indukc pak lze ukazat, ze R1 R2 : : : R qxy ` R10 R20 : : : R0 q 0 y v P prave kdyz (q; xy; (R )(R 1) : : : (R1)) ` (q0; y; (R0 )(R0 1) : : : (R10 )) v A. Oba automaty pak jsou v kazdem kroku ve stejnem stavu a neutraln prvek volne grupy se v registru automatu A objev prave v okamziku, kdyz se vyprazdn zasobnk automatu P . Jazyky generovane automatem A a automatem P DA jsou tedy shodne. Protoze kazda volna grupa je zarove n podgrupou binarn volne grupy, je dukaz hotovy. Dukaz inkluze L(EF A(F2)) CF uved'me jiz pouze strucne. V tomto prpade budeme na pocatku uvazovat libovolny rozsreny konecny automat nad volnou grupou s dvema generatory. Po konstrukci vhodne prave linearn gramatiky dale de nujeme tzv. smesovac operaci (shue operation) o rekurzvne takto: (u o ") = (" o u) = fug a (au o bw) = a(u o bv) [ b(au o v) kde u; v jsou retezce a a; b symboly. Prirozene rozsren teto operace na jazyky provedeme jako [ (u o v ) L1 o L2 = m
n
s
n
m
m
s
2
u
L1 ;v
10
2
L2
s
S vyuzitm Dykova jazyka (Dyck language) radu 2 (viz strana 603 v [3]) a vlastnost uzaveru rodiny bezkontextovych jazyku dokazeme, ze L(A) je skutecne bezkontextovy. Prpadne zajemce odkazujeme na [5], kde je dukaz kompletn. Jiz bez dukazu si uved'me jakysi souhrn teto casti, ktery je prevzat rovnez z [5]. = L(EF A(F0)) L(EF A(F1)) L(EF A(F2)) = CF Zminme se strucne i o deterministickych konecnych automatech nad volnymi grupami. Je vseobecne znamo, ze bezne deterministicke a nedeterministicke konecne automaty maj stejnou vyjadrovac schopnost. Z tohoto pohledu je vsak prekvapujc, ze deterministicke konecne automaty nad volnymi grupami maj mens vyjadrovac slu nez jejich nedeterministicke varianty. Podvame-li se vsak na tuto problematiku ze strany bezkontextovych jazyku, jejichz formalnmi modely jsou i zasobnkove automaty, jedna se vlastne o prirozenou vlastnost, nebot' deterministicke zasobnkove automaty jsou taktez slabs nez jejich nedeterministicke varianty. Vce o teto problematice lze opet najt v [5].
Veta 4.2
4.2
REG
Diskuse ke kone cn ym automat um
V teto kapitole jsme si demonstrovali nektere dals modi kace beznych konecnych automatu. Vidme, ze jejich vhodnym rozsrenm jsme schopni do urcite mry zvysit jejich vyjadrovac schopnosti. Nejsme tedy omezeni pouze trdou regularnch jazyku. V nasledujc kapitole se budeme pro zmenu zabyvat zasobnkovymi automaty a ukazeme, ze podobny prstup je aplikovatelny i v teto oblasti.
11
5 Oboustranne zasobnkove automaty nad volnymi grupami
Mnozina vsech retezcu nad urcitou abecedou je obvykle vyjadrena volnym monoidem generovanym symboly teto abecedy a operac konkatenace. Neutralnm prvkem je pak prazdny retezec ". Nad mnozinou vsech retezcu jsou de novany relace prme derivace a dals souvisejc operace. My vsak volne monoidy castecne opustme. Kazdy prvek puvodn abecedy rozsrme o jeho inverzn variantu a mnozinu vsech retezcu nad nove vzniklou abecedou budeme de novat pomoc volne grupy generovane touto abecedou a operac konkatenace. Krome neutralnho prvku " zskame i inverzn retezce. Konkatenac kazdeho retezce s jeho inverzn variantou pak zskame prave prazdny retezec " (viz de nice 2.4 a 2.5). Tato kapitola je ispirovana clankem [6]. Zavad vsak zcela novy prstup, zjednodusuje konstrukci pravidel automatu a zpruhlednuje dukaz. 5.1
Frontov e gramatiky
Pro de nici a konstrukci oboustrannych zasobnkovych automatu nad volnymi grupami vyuzijeme tzv. frontove gramatiky (viz tez [8]). De nice 5.1 Frontova gramatika je sestice G = (V; T; W; F; s; P ), kde
V a W jsou dve konecne abecedy, pro ktere plat V \ W = ? T V, F W s 2 (V T )(W F ) je axiom P V (W F ) V W je konecna relace takova, ze pro kazde a 2 V existuje prvek (a; b; x; c) 2 P . Jestlize u; v 2 V W jsou retezce tvaru u = arb, v = rxc, kde a 2 V , r; x 2 V , b; c 2 W a (a; b; x; c) 2 P , pak rkame, ze u prmo derivuje v ve frontove gramatice G
podle pravidla (a; b; x; c). Pseme
[( )] Symboly ) , ) a )+ oznacuj postupne derivaci delky n, n 0, tranzitivn uzaver a re exivn-tranzitivn uzaver relace prme derivace `. Jazyk generovany frontovou gramatikou G, je de novan jako L(G) = fw 2 T js ) wf; kde f 2 F g. arb ) rxc a; b; x; c
n
(viz tez [9]) je sestice G = (V; T; W; F; s; P ), kde V; T; W; F a s maj stejny vyznam jako v prpade bezne frontove gramatiky a P V (W F ) V W je konecna relace (poznamenejme, ze tato de nice nevyzaduje, aby pro kazde a 2 V existovalo nejake pravidlo (a; b; x; c) 2 P ). Krome toho predpokladejme, ze # 62 (V [ W ). Jestlize u; v 2 V f#gV W jsou retezce tvaru u = w#arb, v = wa#rxc, kde a 2 V , r; x; w 2 V , b; c 2 W a (a; b; x; c) 2 P , potom pseme w#arb ) wa#rxc[(a; b; x; c)] De nice 5.2 Leve rozsrena frontova gramatika
12
Symboly ) , ) a )+ oznacuj postupne derivaci delky n, n 0, tranzitivn uzaver a re exivn-tranzitivn uzaver relace prme derivace `. Jazyk generovany leve rozsrenou frontovou gramatikou G je de novan jako L(G) = fy 2 T j#s ) w#yf pro nejake w 2 V a f 2 F g. Oznacme QG trdu jazyku generovanych frontovymi gramatikami. Plat nasledujc veta. n
Veta 5.1 QG = RE. Dukaz je mozne nalezt v [8].
Nasledujc pomocna veta bude vyuzita pri konstrukci oboustranneho zasobnkoveho automatu nad volnou grupou. Pro kazdy rekurzvne vycslitelny jazyk L existuje leve rozsrena frontova gramatika G takova, ze L = L(G) a pro kazde pravidlo (a; b; x; c) 2 P plat a 2 (V T ), b 2 (W F ) a x 2 ((V T ) [ T ). Dukaz viz [3].
Lemma 5.2
5.2
Oboustrann e z asobn kov e automaty nad voln ymi
grupami
je n-tice = (Q; T; Z; R; z; Z ; Z ; F ), kde Q je konecna mnozina stavu T je konecna vstupn abeceda Z je konecna zasobnkova abeceda R je konecna mnozina pravidel tvaru Z1jZ2px ! 1j 2q, kde Z1; Z2 2 Z , 1 ; 2 2 Z , x 2 T a p; q 2 Q; poznamenejme, ze takovyto automat muze nactat v jednom vypocetnm kroku vce nez jeden vstupn symbol (transformace na klasicky automat ctouc nejvyse jeden symbol ze vstupu je trivialn) z je pocatecn stav Z resp. Z je pocatecn symbol leve resp. prave strany zasobnku, Z ; Z 2
De nice 5.3 Oboustranny zasobnkovy automat nad volnou grupou M
L
L
Z
FM
R
M
R
L
R
Q je mnozina koncovych stavu
Kon gurac oboustranneho zasobnkoveho automatu nad volnou grupou rozum-
me retezec qw, kde q 2 Q, 2 Z a w 2 T . Pokud L Rpxy a
qy jsou dve kon gurace a LjRpx ! j q 2 R, kde x; y 2 T , p; q 2 Q, L; R 2 Z a ; ; 2 Z , pak automat M provad prechod z kon gurace L Rpxy do kon gurace
qy podle pravidla LjRpx ! j q a pseme L Rpxy `
qy [LjRpx ! j q ] Relace ` , `+ a ` oznacuj posloupnost prechodu delky n, n 0, tranzitivn a re exivn-tranzitivn uzaver relace ` v tomto porad a jsou de novany obvyklym zpusobem. L
L
L
R
R
L
R
L
L
R
R
L
n
13
R
R
Jazyk prijmany oboustrannym zasobnkovym automatem M je de novan jako L(M ) = fwjw 2 T ; Z Z zw ` "f , kde f 2 F g. Vsimneme si, ze retezce vyskytujc se na oboustrannem zasobnku jsou tvoreny volnou grupou generovanou abecedou Z operac konkatenace. R etezec w je automatem prijat pouze tehdy, pokud je beze zbytku nacten, zasobnk je prazdny a automat se po proveden poslednho kroku nachaz v nekterem koncovem stavu. Nyn se jiz dostavame k hlavnmu vysledku tohoto projektu. Oznacme 2PDA trdu jazyku prijmanych oboustrannymi zasobnkovymi automaty nad volnymi grupami. R
L
M
2PDA = RE
Veta 5.3 D ukaz
Je dokazano, ze trda jazyku generovanych frontovymi gramatikami (QG) je totozna s trdou rekurzvne vycslitelnych jazyku (RE). Stac tedy dokazat, ze pro kazdou frontovou gramatiku G = (V; T; W; F; Sq0; P ) je mozne sestrojit oboustranny zasobnkovy automat nad volnou grupou M = (Q; T; Z; R; z; Z ; Z ; F ) takovy, ze L(G) = L(M ). Bez ztraty obecnosti predpokladejme, ze G splnuje podmnky popsane v Lemmatu 5.2. L
R
M
Konstrukci oboustranneho zasobnkoveho automatu nad volnou grupou provedeme aplikac nasledujcch kroku: Q = ff; zg [ fhq; 1i; hq; 2ijq 2 W g Z = fZ ; Z ; Z ; Z g [ (V T ) [ N , kde N = fxjx 2 (V T )g F = ff g Mnozina pravidel R je zkonstruovana nasledujcm zpusobem: 1) pro axiom Sq0 gramatiky G, kde S 2 (V T ), q0 2 (W F ), pridej Z jZ z ! Z jSZ hq0 ; 1i do R 2) pro kazde (A; q; x; p) 2 P , kde A 2 (V T ), p; q 2 (W F ), x 2 (V T ), pridej Z jZ hq; 1i ! Z AjxZ hp; 1i do R 3) pro kazde q 2 W pridej Z jZ hq; 1i ! Z jZ hq; 2i do R 4) pro kazde (A; q; y; p) 2 P , kde A 2 (V T ), p; q 2 (W F ), y 2 T , pridej Z jZ hq; 2iy ! Z AjZ hp; 2i do R 5) pro kazde (A; q; y; t) 2 P , kde A 2 (V T ), p 2 (W F ), t 2 F , pridej Z jZ hq; 2iy ! Aj"f do R Nyn je konstrukce hotova. Pro dals casti dukazu zaved'me nasledujc notaci. Jestlize hq; 1i je aktualn stav automatu M , rkame, ze M je v modu generovan nonterminal u. Podobne jestlize hq; 2i je aktualn stav automatu M , rkame, ze M je v modu cten terminal u (pro nejake q 2 W ). Nyn musme dokazat rovnost L(G) = L(M ), tedy inkluze L(G) L(M ) a L(M ) L(G). Nejprve dokazeme prvn inkluzi, tedy L(G) L(M ). Proved'me to postupnou demonstrac tvrzench A, B a C. Konstrukce
L
R
L
R
M
L
R
L
L
R
R
L
R
L
L
R
L
R
L
R
L
R
14
R
Jestlize A1 : : : A #B1 : : : B u ) A1 : : : A B1 : : : B #B +1 : : : : : : B x1 : : : x p v G, potom Z A : : : A1 A1 : : : A B1 : : : B Z hu; 1i! ` Z B : : : : : : B1 A : : : A1 A1 : : : A B1 : : : B x1 : : : x Z hp; 1i! v M , kde A1 ; : : : ; A , B1 ; : : : ; B 2 (V T ), x1 ; : : : ; x 2 (V T ) , u; p 2 (W F ), m 1, n 0, ! 2 T , i < m. Tvrzen A
n
m
i
n
L
n
i
m
n
m
m
i
i
m
i
i
R
i
L
n
R
i
Necht' i = 0. Potom A1 : : : A #B1 : : : B u )0 A1 : : : #B1 : : : B u v G. Je zrejme, ze Z A : : : A1A1 : : : A B1 : : : B Z hu; 1i! `0 : : : A1 A1 : : : A B1 : : : B Z hu; 1i! v M .
Z aklad indukce
: : : An ZL An
n
n
n
m
n
m
m
n
L
n
m
R
R
Predpokladejme, ze tvrzen A plat pro kazde i l, kde l
Induk cn hypot eza
je kladne cele cslo.
Uvazujme libovolnou derivaci tvaru A1 : : : A #B1 : : : B u ) +1 A1 : : : A B1 : : : B B +1 #B +2 : : : B x1 : : : x x +1 q a vyjadreme ji presneji jako A1 : : : A #B1 : : : B u ) A1 : : : A B1 : : : B #B +1 : : : B x1 : : : x p ) A1 : : : : : : A B1 : : : B B +1 #B +2 : : : B x1 : : : x x +1 q v G, kde l + 2 m. Podle indukcn hypotezy Z A : : : A1A1 : : : A B1 : : : B Z hu; 1i! ` Z B : : : : : : B1 A : : : A1 A1 : : : A B1 : : : B x1 : : : x Z hp; 1i! ` Z B +1 B : : : : : : B1 A : : : A1 A1 : : : A B1 : : : B x1 : : : x x +1 Z hq; 1i! v M . V P existuje pouze jeden typ pravidel schopny provest derivaci A1 : : : A B1 : : : B #B +1 : : : B x1 : : : : : : x p ) A1 : : : A B1 : : : B B +1 #B +2 : : : B x1 : : : x x +1 q v G. Jsou to pravidla tvaru (B +1; p; x +1; q) 2 P , kde B +1 2 (V T ), p; q 2 (W F ) a x +1 2 (V T ). Podle druheho bodu konstrukce existuje v R pravidlo Z jZ hp; 1i ! Z B +1 jx +1 Z hq; 1i, takze Z B : : : B1 A : : : A1 A1 : : : A B1 : : : B x1 : : : : : : x Z hp; 1i! ` Z B +1 B : : : B1 A : : : A1 A1 : : : A B1 : : : B x1 : : : : : : x x +1 Z hq; 1i! v M a tvrzen A tedy plat. Induk cn krok
n
n
l
n
l
l
l
m
n
l
l
m
l
n
l
m
l
l
l
m
l
l
l
n
L
n
n
n
m
l
R
n
n
m
l
l
m
n
l
l
l
L
l
L
l
m
l
l
m
l
l
l
l
L
L
l
R
l
l
R
l
l
l
R
l
l
l
R
n
l
l
m
L
L
l
n
l
n
n
l
R
m
n
m
R
Jestlize A1 : : : A #B1 : : : B a1 : : : a u ) A1 : : : A B1 : : : : : : B #B +1 : : : B a1 : : : a b1 : : : b p v G, potom Z A : : : A1 A1 : : : A B1 : : : : : : B Z hu; 2ib1 : : : b ` Z B : : : B1 A : : : A1 A1 : : : A B1 : : : B B +1 : : : : : : B Z hp; 2ib +1 : : : b v M , kde A1 ; : : : ; A ; B1 ; : : : ; B 2 (V T ), a1 ; : : : ; a , b1 ; : : : ; b 2 T , u; p 2 (W F ), i < m, i < j , k 0. Claim B i
n
i
m
R
m
R
m
m
i
k
i
j
i
L
i
k
i
n
n
L
n
n
n
j
n
i
i
m
k
j
Necht' i = 0. Potom A1 : : : A #B1 : : : B a1 : : : a u )0 A1 : : : #B1 : : : B a1 : : : a u v G. Je zrejme, ze take Z A : : : A1A1 : : : A B1 : : : Z hu; 2ib1 : : : b `0 Z A : : : A1 A1 : : : A B1 : : : B Z hu; 2ib1 : : : b v M .
Z aklad indukce
: : : An : : : Bm
n
m
j
R
je kladne cele cslo.
Induk cn krok
L
n
n
k
n
m
n
j
R
Predpokladejme, ze tvrzen B plat pro vsechna i l, kde
Induk cn hypot eza
l
m
L
k
Uvazujme libovolnou derivaci tvaru A1 : : : A #B1 : : : B
a1 : : :
) +1 A1 : : : A B1 : : : B B +1#B +2 : : : B a1 : : : a b1 : : : b b +1q a vyjadreme ji presneji jako A1 : : : A #B1 : : : B a1 : : : a u ) A1 : : : A B1 : : : B #B +1 : : : : : : B a1 : : : a b1 : : : b p ) A1 : : : A B1 : : : B B +1 #B +2 : : : B a1 : : : a b1 : : : : : : b b +1 q v G, kde l + 2 m, k 0, i < j , l + 2 j .
: : : ak u
l
n
n
l
l
m
l
k
l
m
l
n
m
n
k
l
l
15
l
k
l
l
l
n
l
m
m
l
k
l
Podle indukcn hypotezy Z
2 ` 2 2 v . V tomto prpade existuje pouze jedna moznost jak muze G provest derivaci A1 : : : A B1 : : : B #B +1 : : : B a1 : : : a b1 : : : b p ) A1 : : : A B1 : : : : : : B B +1 #B +2 : : : B a1 : : : a b1 : : : b b +1 q , a to pomoc pravidla tvaru (B +1 ; p; b +1 ; q ) 2 P , kde B +1 2 (V T ), p; q 2 (W F ), b +1 2 T . Podle ctvrteho bodu konstrukce existuje v R pravidlo Z jZ hp; 2ib +1 ! Z B +1jZ hq; 2i, takze Z B : : : B1 A : : : A1 A1 : : : A B1 : : : B Z hp; 2ib +1 : : : b ` Z B +1 B : : : : : : B1 A : : : A1 A1 : : : A B1 : : : B Z hq; 2ib +2 : : : b v M a tvrzen B plat. An : : : A1 A1 : : : An B1 : : : Bm ZR hu; ib1 : : : bj ZL Bl : : : B1 An : : : A1 A1 : : : An B1 : : : Bm ZR hp; ibl+1 : : : bj ` ZL Bl+1 Bl : : : B1 An : : : A1 A1 : : : An B1 : : : Bm ZR hq; ibl+2 : : : bj M
l
L
n
l
l
l
l
m
l
m
l
k
k
l
n
l
l
l
l
l
L
L
n
l
n
n
n
m
m
R
R
R
L
l
j
l
l
R
l
L
l
l
j
Jestlize # # v , kde ), , ( ), , potom 2 = v , kde . Gramatika G provad popsanou derivaci pomoc pravidla tvaru (A ; q; z; t) 2 P , kde A 2 (V T ), z 2 T , q 2 (W F ), t 2 F . Podle pateho bodu konstrukce existuje v R pravidlo Z jZ hq; 2iz ! A j"f , takze odpovdajc krok popsany tvrzenm C se nepochybne v M vyskytuje. Tvrzen C tedy plat. Dohromady tvrzen A, B a C dokazuj, ze skutecne L(G) L(M ). Abychom dokazali opacnou inkluzi, tedy L(M ) L(G), demonstrujeme postupne platnost tvrzench D, E a F. A1 : : : An 1 An yq ) A1 : : : An 1 An yzt G A1 ; : : : : : : ; An 2 V T y; z 2 T q 2 W F t 2 F ZL An 1 : : : A1 A1 : : : : : : An ZR hq; iz ` An : : : A1 A1 : : : An f "f M f 2 FM
Claim C
(
n
n
L
Claim D
R
n
Automat M prijma kazdy retezec w 2 L(M ) nasledujcm zpusobem.
ZL ZR zw1 w2 : : : wr ` ZL SZR hq0 ; iw1 w2 : : : wr ` ZL SSX11 X21 : : : Xn11 ZR hq1 ; iw1 w2 : : : wr ` ZL X11 SSX11 X21 : : : Xn11 X12 X22 : : : Xn22 ZR hq2 ; iw1 w2 : : : wr ` ZL X21 X11 SSX11 X21 : : : Xn11 X12 X22 : : : Xn22 X13 X23 : : : Xn33 ZR hq3 ;
1
1
1
1i w 1 w 2 : : : w ` r
::: ::: ::: ZL Xjk : : : X21 X11 SSX11 X21 : : : Xn11 X12 X22 : : : Xn22 X13 X23 : : : Xn33 : : : : : : X1m X2m : : : Xnmm ZR hqm ; iw1 w2 : : : wr `
1
ZL Xjk : : : X21 X11 SSX11 X21 : : : Xn11 X12 X22 : : : Xn22 X13 X23 : : : Xn33 : : : : : : X1m X2m : : : Xnmm ZR hqm ; iw1 w2 : : : wr `
2
ZL Xjk+1 Xjk : : : X21 X11 SSX11 X21 : : : Xn11 X12 X22 : : : : : : Xn22 X13 X23 : : : Xn33 : : : X1m X2m : : : Xnmm ZR hqm+1 ;
2 iw 2 : : : w ` r
ZL Xjk+2 Xjk+1 Xjk : : : X21 X11 SSX11 X21 : : : Xn11 X12 X22 : : : : : : Xn22 X13 X23 : : : Xn33 : : : X1m X2m : : : Xnmm ZR hqm+2 ; iw3 : : : wr
2
16
`
::: ::: ::: ZL Xnmm 1 : : : : : : Xjk+2 Xjk+1 Xjk : : : X21 X11 SSX11 X21 : : : Xn11 X12 X22 : : : : : : Xn22 X13 X23 : : : Xn33 : : : X1m X2m : : : Xnmm ZR hqm+r 1 ; iwr `
2
Xnmm Xnmm 1 : : : : : : Xjk+2 Xjk+1 Xjk : : : X21 X11 SSX11 X21 : : : Xn11 X12 X22 : : : : : : Xn22 X13 X23 : : : Xn33 : : : X1m X2m : : : Xnmm f "f
=
v M , kde w = w1w2 : : : w , r 1, w1; : : : ; w 2 T , q0; q1; : : : ; q + 1 2 (W F ), X11 ; : : : ; X 11 ; X12 ; : : : ; X 22 ; : : : ; X1 ; : : : ; X m 2 (V T ), n1 ; n2 ; : : : ; n 0, m 1, 0 k m. r
r
m
n
m
r
m n
n
m
Nyn prozkoumame vsechny kroky konstrukce mnoziny automatovych pravidel R. Poznamenejme, ze v kazdem uspesnem vypoctu automat M pouzva vzdy pravidla zkonstruovana v kroku b pred tm, nez pouzije pravidla zkonstruovana v kroku b + 1, pro b = 1; : : : ; 4. V prvnm kroku aplikuje M pravidlo Z jZ z ! Z jSZ hq0; 1i zkonstruovane v casti 1, kde Sq0 je axiom gramatiky G. Toto je jediny zpusob, kterym muze M provest prechod Z Z zw1 w2 : : : w ` Z SZ hq0 ; 1iw1 w2 : : : w . Vsimneme si, ze v kazdem uspesnem vypoctu automatu je toto pravidlo pouzito prave jednou. Pomoc nej se automat zaroven prepne do modu generovan nonterminalu. V dals casti vypoctu popsane sekvenc prechodu Z SZ hq0 ; 1iw1 w2 : : : w ` Proof of Claim D
L
L
L
R
r
R
R
L
L
R
r
R
r
ZL Xjk : : : X21 X11 SSX11 X21 : : : Xn11 X12 X22 : : : Xn22 X13 X23 : : : Xn33 : : : : : : X1m X2m : : : Xnmm ZR hqm ; iw1 w2 : : : wr
1
pouzva M pravidla tvaru Z jZ hq; 1i ! Z AjxZ hp; 1i zkonstruovana v bodu 2, kde A 2 (V T ), x 2 (V T ), p; q 2 (W F ). Tato cast vypoctu je charakterizovana stavy automatu tvaru hq; 1i, q 2 (W F ). Detailn dukaz teto casti je uveden v tvrzen E. V kroku L
R
R
L
ZL Xjk : : : X21 X11 SSX11 X21 : : : Xn11 X12 X22 : : : Xn22 X13 X23 : : : Xn33 : : : : : : X1m X2m : : : Xnmm ZR hqm ; iw1 w2 : : : wr `
1
ZL Xjk : : : X21 X11 SSX11 X21 : : : Xn11 X12 X22 : : : Xn22 X13 X23 : : : Xn33 : : : : : : X1m X2m : : : Xnmm ZR hqm ; iw1 w2 : : : wr
2 automat M prepne pomoc pravidla tvaru Z jZ hq; 1i ! Z jZ hq; 2i zkonstruovaneho v bodu 3 do modu cten nonterminalu. Poznamenejme, ze toto pravidlo je behem jednoho uspesneho vypoctu automatu pouzito prave jednou. Protoze je jeho aplikac zmenen aktualn stav automatu tvaru hq; 1i na stav tvaru hq; 2i, q 2 (W F ), nen jiz zadna dals moznost pouzit pravidel zkonstruovanych v bodech 1 az 3. V dals casti vypoctu popsane sekvenc kroku L
17
R
L
R
ZL Xjk : : : X21 X11 SSX11 X21 : : : Xn11 X12 X22 : : : Xn22 X13 X23 : : : Xn33 : : : : : : X1m X2m : : : Xnmm ZR hqm ; iw1 w2 : : : wr `
2
ZL Xnmm 1 : : : : : : Xjk+2 Xjk+1 Xjk : : : X21 X11 SSX11 X21 : : : Xn11 X12 X22 : : : : : : Xn22 X13 X23 : : : Xn33 : : : X1m X2m : : : Xnmm ZR hqm+r 1 ; iwr
2 pouzva M pravidla zkonstruovana v bodu 4 a postupne nacta vstupn retezec. Podrobny dukaz teto casti je uveden v tvrzen F. Poslednm krokem automat prejde do koncoveho stavu f 2 F pomoc nejakeho pravidla tvaru Z jZ hq; 2iy ! Aj"f zkonstruovaneho v bodu 5, kde q 2 (W T ), y 2 T a A 2 (V T ). Pokud je oboustranny zasobnk po proveden tohoto kroku prazdny (po aplikaci grupovych redukc), pak byl vstupn retezec prijat. V opacnem prpade retezec prijat nen, nebot' v mnozine R neexistuje zadne pravidlo obsahujc f 2 F na sve leve strane. M
L
R
M
Jestlize Z
1 1 v , potom v , kde ( ), .
An : : : A1 A1 : : : An B1 : : : Bm ZR hu; i! `i ZL Bi : : : : : : B1 An : : : A1 A1 : : : An B1 : : : Bm x1 : : : xi ZR hp; i! M A1 : : : An B1 : : : i : : : Bm u ) A1 : : : An B1 : : : Bi Bi+1 : : : Bm x1 : : : xi p G A1 ; : : : ; An ; B1 ; : : : : : : ; Bm 2 V T x1 ; : : : ; xi 2 V T u; p 2 W F i < m
Claim E
L
(
#
),
(
),
#
Necht' i = 0. Pak Z A : : : A1A1 : : : A B1 : : : B Z hu; 1i! `0 : : : A1 A1 : : : A B1 : : : B Z hu; 1i! v M . Rozhodne take A1 : : : A #B1 : : : u )0 A1 : : : A #B1 : : : B u v G.
Z aklad indukce
n
m
n
Induk cn hypot eza
l
n
L
ZL An : : : Bm
je kladne cele cslo.
n
m
R
n
R
m
Predpokladejme, ze tvrzen E plat pro vsechna i l, kde
Uvazujme libovolnou posloupnost kroku tvaru 1 1 a vyjadreme ji presneji jako 1 1 1 v , kde ( ), + 2 . Podle indukcn hypotezy A1 : : : A #B1 : : : B u ) A1 : : : A B1 : : : B #B +1 : : : : : : B x1 : : : x p ) A1 : : : A B1 : : : B B +1 #B +2 : : : B x1 : : : x x +1 q v G. V mnozine R je pouze jeden typ pravidel schopnych provest posloupnost kroku Z B : : : : : : B1 A : : : A1 A1 : : : A B1 : : : B x1 : : : x Z hp; 1i! ` Z B +1 B : : : B1 A : : : : : : A1 A1 : : : A B1 : : : B x1 : : : x x +1 Z hq; 1i! v M . Jsou to pravidla tvaru Z jZ hp; 1i ! Z B +1 jx +1 Z hq; 1i 2 R. Podle konstrukce vsak existuje v G pravidlo tvaru (B +1; p; x +1; q) 2 P , takze rovnez A1 : : : A #B1 : : : B u ) A1 : : : A B1 : : : B #B +1 : : : B x1 : : : x p ) A1 : : : A B1 : : : B B +1 #B +2 : : : : : : B x1 : : : x x +1 q v G a tvrzen E plat.
Induk cn krok ZL An : : : A1 A1 : : : : : : An B1 : : : Bm ZR hu; i! `l+1 ZL Bl+1 Bl : : : B1 An : : : A1 A1 : : : An B1 : : : Bm x1 : : : : : : xl xl+1 ZR hq; i! ZL An : : : A1 A1 : : : An B1 : : : l : : : Bm ZR hu; i! ` ZL Bl : : : B1 An : : : A1 A1 : : : An B1 : : : Bm x1 : : : xl ZR hp; i! ` ZL Bl+1 Bl : : : B1 An : : : A1 A1 : : : An B1 : : : Bm x1 : : : xl xl+1 ZR hq; i! M q2 W F l m
n
m
n
l
m
l
l
l
n
m
l
l
l
l
l
L
n
n
n
L
m
R
L
l
n
l
l
l
l
l
m
m
R
l
l
L
l
R
R
n
l
m
l
l
n
l
n
l
l
m
l
l
l
l
Jestlize Z
2
An : : : A1 A1 : : : An B1 : : : Bm ZR hu; ib1 : : : bj `i ZL Bi : : : : : : B1 An : : : A1 A1 : : : An B1 : : : Bi Bi+1 : : : Bm ZR hp; ibi+1 : : : bj M A1 : : : : : : An B1 : : : Bm a1 : : : ak u )i A1 : : : An B1 : : : Bi Bi+1 : : : Bm a1 : : : ak b1 : : : bi p G A1 ; : : : ; An ; B1 ; : : : ; Bm 2 V T a1 ; : : : ; ak ; b1 ; : : : ; bj 2 T C; D 2 W F i<m
Claim F
# , kde ,
L
,
.
18
2 #
v , potom a
v
Necht' i = 0. Pak Z A : : : A1A1 : : : A B1 : : : B Z hu; 2ib1 : : : b `0 : : : A1 A1 : : : A B1 : : : B Z hu; 2ib1 : : : b v M . Je zrejme, ze A1 : : : A #B1 : : : a1 : : : a u )0 A1 : : : A #B1 : : : B a1 : : : a u v G.
Z aklad indukce
ZL An : : : Bm
m
n
m
j
R
j
R
n
k
n
m
k
Predpokladejme, ze tvrzen F plat pro vsechna i l, kde
Induk cn hypot eza
l
n
L
n
je kladne cele cslo.
Uvazujme libovolnou posloupnost kroku tvaru 2 2 a vyjadreme ji presneji jako 2 2 2 v , kde + 2 . Podle indukcn hypotezy A1 : : : A #B1 : : : B a1 : : : a u ) A1 : : : A B1 : : : : : : B #B +1 : : : B a1 : : : a b1 : : : b p ) A1 : : : A B1 : : : B B +1 #B +2 : : : : : : B a1 : : : a b1 : : : b b +1 q v G, kde l + 2 m. V tomto prpade existuje pouze jeden zpusob jak muze M provest krok Z B : : : : : : B1 A : : : A1 A1 : : : A B1 : : : B Z hp; 2ib +1 : : : b ` Z B +1 B : : : B1 A : : : : : : A1 A1 : : : A B1 : : : B Z hq; 2ib +2 : : : b a sice pomoc nejakeho pravidla tvaru Z jZ hp; 2ib +1 ! Z B +1 jZ hq; 2i 2 R. Podle konstrukce obsahuje P pravidlo tvaru (B +1; p; b +1; q), kde B +1 2 (V T ), p; q 2 (W F ), b +1 2 T , takze A1 : : : A B1 : : : B #B +1 : : : B a1 : : : a b1 : : : b p ) A1 : : : A B1 : : : B B +1 # B +2 : : : B a1 : : : a b1 : : : b b +1 q v G a tvrzen F tedy plat. Tvrzen D, E a F dokazuj, ze skutecne L(M ) L(G). Celkove potom L(G) = L(M ), cmz je veta dokazana.
Induk cn krok ZL An : : : A1 A1 : : : : : : An B1 : : : Bm ZR hu; ib1 : : : bj `l+1 ZL Bl+1 Bl : : : B1 An : : : A1 A1 : : : : : : An B1 : : : Bm ZR hq; ibl+2 : : : bj ZL An : : : : : : A1 A1 : : : An B1 : : : Bm ZR hu; ib1 : : : bj `l ZL Bl : : : B1 An : : : A1 A1 : : : : : : An B1 : : : Bm ZR hp; ibl+1 : : : bj ` ZL Bl+1 Bl : : : B1 An : : : A1 A1 : : : An B1 : : : : : : Bm ZR hq; ibl+2 : : : bj M l j n
l
m
l
m
k
k
l
m
n
l
l
k
l
l
L
l
n
l
l
L
n
n
n
L
R
5.3
L
R
j
l
R
l
m
l
k
l
n
l
j
l
l
m
R
l
l
n
l
m
l
l
m
l
l
k
l
n
l
l
l
Diskuse k z asobn kov ym automat um
Podobne jako v prpade konecnych automatu, lze doclit zvysen vyjadrovac schopnosti i pro zasobnkove automaty. Uvedena modi kace na dvouzasobnkovy automat nen jedina. Dokonce ani volna grupa, ktera generuje mozne retezce vyskytujc se na zasobnku, nen pro spravnou funkci nutna. Msto n bychom mohli pridat jednoducha pravidla odstranujc vzdy levy a pravy vrchol zasobnku. Tato pravidla by mohla byt aplikovana na samem konci vypoctu a zajist'ovala by vyprazdnen zasobnku. Jakmile by nastala situace, ze se levy a pravy vrchol zasobnku neshoduj, cely proces by byl zablokovan a vysledkem by bylo neprijet vstupnho retezce. Naopak, v prpade uplneho vyprazdnen zasobnku a prechodem do koncoveho stavu, by byl retezec prijat. Dalsm vylepsenm tohoto automatu muze byt naprklad redukce poctu symbolu zasobnkove abecedy. Kazdy symbol by byl pote kodovan vhodnym binarnm kodem. Uvedeny prstup pro zvysen vyjadrovacch schopnost zasobnkovych automatu vsak nen jediny. Dals modi kac se zabyva [9]. Zde autori predstavuj tzv. rzene zasobnkove automaty. S vyuzitm vhodneho rdcho jazyka opet zvysuj akceptacn schopnosti beznych zasobnkovych automatu. Prpadne zajemce o tuto problematiku odkazujeme na [9]. 19
6 Zaver
Prezentovany dokument ukazuje, ze soucasne automaty mohou tvorit jakysi zaklad pro dals formaln modely a vhodnymi modi kacemi, omezenmi a rozsrenmi muzeme zvysovat jejich vyjadrovac schopnosti. Posledn prezentovany vysledek navc ukazuje, ze vhodnou modi kac bezneho zasobnkoveho automatu dosahneme u nove vznikleho modelu sly Turingova stroje. Prpadne modi kace Turingova stroje za ucelem mozneho zvysen jeho vyjadrovacch schopnost jsou vsak jiz bezpredmetne, nebot' jak plyne z Turingovy teze, za tuto hranici se jiz nelze dostat. Prkladem muze byt vcepaskovy Turinguv stroj. Prestoze ten urcitym zpusobem rozsiruje pamet'ove moznosti bezneho jednopaskoveho Turingova stroje, lze kazdy vcepaskovy Turinguv stroj transformovat na ekvivalentn Turinguv stroj jednopaskovy. Vyjadrovac schopnost tedy nebyla zadnym zpusobem ovlivnena. Obdobny prstup ke zvysovan vyjadrovacch schopnost je vsak aplikovatelny nejen v oblasti automatu, ale taktez v oblasti gramatik. Stac jen zvolit vhodny zaklad. Vezmeme-li naprklad bezkontextovou gramatiku, muzeme zavedenm urciteho stupne rzen taktez zvysit jej slu. Prkladem tohoto mohou byt naprklad programovane a maticove gramatiky, gramaticke systemy, nebo bezkontextove gramatiky nad volnymi grupami prezentovane v jinem projektu.
20
Reference
[1] Salomaa, A.: Formal Languages. Academic Press, New York, 1973. [2] Jacobson, N.: Basic Algebra, 2nd ed. W.H. Freeman, New York, 1989. [3] Meduna, A.: Automata and Languages: Theory and Applications. Springer, London, 2000. [4] The Accepting Power of Finite Automata Over Groups. TUCS Technical Report No 70, November 1996. [5] Dassow, J., Mitrana, V.: Finite Automata Over Free Groups. Int. Journal of Algebra and Computation Vol. 10, No. 6, 2000, pp. 725-737. [6] Meduna, A.: Simultaneously One-Turn Two-Pushdown Automata. International Journal of Computer Mathematics, No. 82 Taylor & Francis Informa plc, GB, 2003, pp. 1-9. [7] Paun, G.: A New Generative Device: Valence Grammars. Rev Roum. Math. Pures et Appl. 25 (6) (1980), pp. 911-924. Acta Cybernetica, 14, 2000, pp. 653-664. [8] Kleijn, H. C. M., Rozenberg, G.: On the Generative Power of Regular Pattern Grammars. Acta Informatica, 20 (1983), pp. 391-411. [9] Meduna, A., Kolar, D.: Regulated Pushdown Automata. Acta Cybernetica, 14 (2000), pp. 653-664.
21
