Siedma sada domacich uloh

Ulohy 4 a 7 su urcene na odovzdavanie a nie je mozne ich prezentovat. Odovzdavajte ich do stredy 5. 4. rana (t.j. 8:10) do skatule na chodbe pred sekretariatom katedry informatiky.
V ulohach 1 - 3 zostrojte bezkontextovu gramatiku G generujucu doplnok k danemu jazyku L, t.j. L(G) = LC.
V ulohach 1 - 2 je dany PKP {xi,yi}, i=1,...,n, slova xi a yi su z {a,b}+. Jazyk L je nad abecedou {a,b,c,1,...,n}.

Uloha 1

L = Lxy = { xi1xi2...xikcik...i2i1cj1j2...jlcyjl...yj2yj1 | 1<= ip, jq <= n }

Uloha 2

L = Lsym = { xi1xi2...xikcjl...j2j1cj1j2...jlcyik...yi2yi1 | 1<= ip, jq <= n }

Uloha 3

Dany je TS A. 
L = Lplatne vypocty A = { v1#v2#...#vk | v2i a v2i+1R su konfiguracie TS A
                      a plati: z v2i sa da jednym krokom vypoctu dostat do v2i+1R
                      a zaroven sa z v2i-1R da dostat jednym krokom vypoctu do v2i }

Uloha 4

(*odovzdavacia uloha)
Dany je TS A. Zostrojte bezkontextove gramatiky G1 a G2 take, ze prienik jazykov L(G1) a L(G2) je rovny jazyku Lplatne vypocty A (definicia v predoslej ulohe).
V ulohach 5 a 6 zistite, ci je dana trieda jazykov uzavreta na operaciu prefixu. Tato operacia je definovana nasledovne: 
Pref(L) = { w | existuje u take, ze wu patri do L, u,w su slova nad abecedou Sigma }

Uloha 5

Trieda bezkontextovych jazykov.

Uloha 6

Trieda kontextovych jazykov.

Uloha 7

(*odovzdavacia uloha)
Predpokladajte, ze mate dany algoritmus (deterministicky TS, ktory vzdy zastavi), ktory pre lubovolnu bezkontextovu gramatiku G rozhodne, ci je jazyk L(G) regularny. Na zaklade tohto algoritmu zostrojte algoritmus pre riesenie Postovho Korespondencneho Problemu.