7. Sada domacich uloh

Uloha 1 (prez.)

Dokazte, ze problem konecnosti jazyka je pre bezkontextove jazyky rozhodnutelny.

Uloha 2 (prez.)

Dokazte, ze ak je prienik jazykov L(x,y) a L_SYM neprazdny, potom nie je bezkontextovy.

Uloha 3 (prez.)

Pomocou jazykov platnych (neplatnych) vypoctov dokazte, ze problem "=Sigma " je pre bezkontextove jazyky nerozhodnutelny.

Uloha 4 (prez.)

Uvazujme jazyk L_U ={<M,w> | w \in L(M) } (teda jazyk univerzalneho turingovho stroja).

Dokazte, ze:

a) L_U je rekurzivne vycislitelny, ale nie je rekurzivny.

b) Komplement jazyka L_U nie je rekurzivne vycislitelny.

Uloha 5 (prez)

Nech je dany TS A. Dokazte, ze jazyk neplatnych vypoctov L_NPV(A)je bezkontextovy.

Uloha 6

Dokazte, ze PKP nad jednopismenovou abecedou je rozhodnutelny.

Uloha 7

Je rozhodnutelne, ci TS dosiahne pre dany vstup w danu konfiguraciu uqv, kde u,v su slova nad paskovou abecedou a q je stav ?