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!

  1. 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}.)
  2. 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.
  3. 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.)
  4. 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.
  5. 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
  6. Dokážte, že trieda LREC je uzavretá na komplement.
  7. 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.
  8. 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ú).
  9. Daný je nedeterministický TS A. Zostrojte ekvivalentný TS A', ktorého každý výpočet je buď akceptujúci, alebo nekonečný.