9. 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.

  1. Upravte algoritmus CYK (Cocke, Younger, Kasami) tak, aby pre každé slovo, ktoré patrí do jazyka L(G), vyrobil strom odvodenia pre toto slovo.
  2. Daná je bezkontextová gramatika G = ({S,A,B,C},{a,b,c,d},P,S) s pravidlami: 
    S -> ASBS | C | epsilon
A -> aAb | epsilon
B -> cA | bB
C -> SdS
    Pomocou algoritmu CYK zistite, či slovo abcdab patri do L(G).
  3. Dokážte alebo vyvráťte:
    Je rozhodnuteľné, či komplement bezkontextového jazyka je bezkontextový.
  4. Zistite (a dokážte), či je pre bezkontextové gramatiky rozhodnuteľný problém:
    Obsahuje L(G) slovo párnej dĺžky?
  5. Zistite (a dokážte), či je pre bezkontextové gramatiky rozhodnuteľný problém:
    Zistiť, či pre dané dva bezkontextové jazyky L1, L2 (dane gramatikami) platí, že L1 je podmnožinou L2.
  6. Zistite (a dokážte), či je rozhodnuteľný problém:
    Zistiť, či pre dany regulárny jazyk L1 a bezkontextovy jazyk L2 (dane gramatikami) platí, že
    a) L1 je podmnožinou L2.
    b) L2 je podmnožinou L1.
  7. (pre fajnšmekrov) Uvažujme TS, ktorý môže na pásku zapisovať iba znak 'a' (a nemôže zapisovať blank). Zaraďťe triedu jazykov rozpoznávaných takýmito automatmi do Chomského hierarchie.