Jedenasta sada domacich uloh

Ulohy 3 a 7 su urcene na odovzdavanie a nie je mozne ich prezentovat. Odovzdavajte ich do stredy 3. 4. rana (t.j. 8:10) do skatule na chodbe pred sekretariatom katedry informatiky.

Uloha 1

Dokazte alebo vyvratte: deterministicke bezkontextove jazyky su uzavrete na operaciu minima jazyka.
Jazyk L' je minimum jazyka L, ak L' obsahuje vsetky slova w z jazyka L, ktore nie su prefixom ziadneho ineho slova z L.

Uloha 2

(pre fajnsmekrov :) )
Dokazte alebo vyvratte: bezkontextove jazyky su uzavrete na operaciu minima jazyka. (definicia vid. predch. uloha)

Uloha 3

(*odovzdavacia uloha)
O kazdom z nasledujucich problemov urcite, ci je rozhodnutelny. Svoje tvrdenie zdovodnite.
  1. Pre dany deterministicky bezkontextovy jazyk L1 a regularny jazyk L2 urcit, ci sa rovnaju
  2. Pre dany deterministicky bezkontextovy jazyk L1 a regularny jazyk L2 urcit, ci L1 je podmnozinou L2.
  3. Pre dane deterministicke bezkontextove jazyky L1 a L2 urcit, ci maju neprazdny prienik.

Uloha 4

Najdite bezkontextovy jazyk, ktory nie je deterministicky ale jeho komplement je bezkontextovy.

Uloha 5

Dokazte alebo vyvratte: trieda deterministickych bezkontextovych jazykov je uzavreta na operaciu reverzu.

Uloha 6

Zostrojte deterministicky Turingov stroj s neprepisovatelnou vstupnou paskou, ktory pre vstup w dlzky n>1 na pracovnej paske oznaci hornu celu cast log2 n znakov. Za oznacene sa povazuje kazde policko, na ktorom nie je blank (TS nemoze zapisovat blanky).

Uloha 7

(*odovzdavacia uloha)
Zostrojte polozkovy automat pre gramatiku 
S -> Ad
A -> aAa | Bb | Cc
B -> d
C -> d

Uloha 8

Dokazte, ze trieda jazykov DSPACE(log(n)) je uzavreta na zjednotenie.

Uloha 8

Dokazte, ze trieda jazykov DTIME(n2) je uzavreta na zjednotenie.