6. séria domácich úloh
Pokiaľ nie je povedané ináč, všetky jazyky, gramatiky a automaty v zadaniach
sú všeobecné (t.j. môžu byť ľubovoľné). Pokiaľ bola odprednášaná štandardná
konštrukcia, používajte ju! V opačnom prípade musíte zdôvodniť správnosť
svojej konštrukcie. V zadaní úlohy, ktorú chcete odovzdať ako "veľkú"
prezentáciu si prípadné slovo zdôvodnite nahraďte slovom dokážte.
Znakom C označujeme cent a znakom S dolár.
Odovzdávacie úlohy je potrebné odovzdať do
stredy 27.3.2002 8:00 do krabice pre sekretariátom KI!
- Odovzdávacia.
Daná je n-tica slov X=(x1, ..., xn) nad abecedou {a,b}. Označme jazyk
LX = { xi_1...xi_kcai_kbai_(k-1)b...ai_1b
| k>=1 a pre vsetky j plati 1<=i_j<=n }
(Neformálne povedané, jazyk je tvorený slovami, ktorých prvú časť tvorí niekoľko slov množiny X, nasleduje
znak c a indexy použitých slov v opačnom poradí, pričom indexy sú kódované ako exponenty, t.j. počtom znakov a.)
a) Zostrojte bezkontextovú gramatiku, generujúcu jazyk LX a zdôvodnite správnosť svojej konštrukcie.
b) Zostrojte bezkontextovú gramatiku, generujúcu jazyk LXC a zdôvodnite správnosť svojej
konštrukcie, prípadne dokážte, že tento jazyk nie je bezkontextový.
(Komplement berieme nad abecedou {a,b,c}.)
- Odovzdávacia.
Dané sú dva deterministické TS A1, A2 a slovo w. Zostrojte deterministický TS A3,
ktorý na ľubovoľnom vstupnom slove x bude pracovať nasledovne:
-- Ak A1 akceptuje slovo w, tak A3 sa na vstupe x bude správať rovnako ako A2
(t.j. akceptuje ho práve vtedy, keď by ho akceptoval A2).
-- Ak A1 neakceptuje slovo w, tak A3 slovo x neakceptuje.
-
Dokážte, že kontextové gramatiky, ktorých pravidlá sú tvaru uAv->uxv, kde A je neterminál, u,v,x sú ľubovoľné slová
nad (N u T) a x nie je prázdne, sú normálnym tvarom pre kontextové gramatiky. (Z tohoto normálneho tvaru pochádza
názov "kontextové gramatiky" -- prepisuje sa neterminál, nachádzajúci sa v kontexte u,v.)
-
Dokážte, že kontextové gramatiky, ktorých pravidlá sú tvaru u->v, u,v sú ľubovoľné slová nad (N u T),
|u|<=|v|<=2, sú normálnym tvarom pre kontextové gramatiky.
-
Daný je deterministický TS A a slovo w. Zostrojte det. TS A', ktorý bude na každom vstupnom slove x pracovať
nasledovne:
-- Ak A akceptuje w, tak A' akceptuje x
-- Ak A neakceptuje w, tak A' neakceptuje x
-
Dokážte, že trieda LREC je uzavretá na komplement.
-
Nech G je kontextová gramatika. Slovo w je odvodené ľavým krajným odvodením v G, ak sa v každom kroku odvodenia
použije pravidlo, ktoré prepisuje najľavejší neterminál vetnej formy. Označme Left(G) jazyk slov, pre ktoré existuje
ľavé krajné odvodenie v G. Ďalej označme LLEFT triedu týchto jazykov, t.j.
LLEFT = { Left(G) | G je kontextová }
Zaraďte triedu LLEFT do Chomského hierarchie, t.j. porovnajte ju s triedami LCS, LCF
a ak treba, tak aj s R.
-
Zostrojte det. TS, ktorý bude počítať hornú celú časť čísla log2n. Vstup aj výstup je kódovaný
v unárnej sústave, t.j. kód čísla n je slovo, pozostávajúce z (n+1) znakov 1. To, že stroj počíta danú funkciu,
znamená, že keď má na začiatku na páske (korektne zadané) vstupné slovo, po konečnom čase skončí v akceptačnom
stave, pričom na páske bude zapísaná výstupná hodnota (falošné blanky na koncoch pásky sa ignorujú).
-
Daný je nedeterministický TS A. Zostrojte ekvivalentný TS A', ktorého každý výpočet je buď akceptujúci, alebo
nekonečný.