6. Sada domacich uloh

Uloha 1 (prez.)

Nech L je deterministicky bezkontextovy jazyk a R je regularny jazyk. Dokazte ze,

1. L prienik R \in L_detCF
2. Min(L) \in L_detCF ,kde min(L) = {w \in L | pre vsetky x,y take, ze w=xy a x \in L, plati ze y = \epsilon}

Uloha 2 (prez.)

Dokazte, ze L_detCF nie je uzavreta na zjednotenie.

[Navod: Porozmyslajte o jazyku {aⁱb^jc^k | i=j alebo j=k}]

Uloha 3 (prez.)

Zasobnikovy automat A je jednoznacny, ak pre kazde w \in L(A) existuje prave jeden akceptacny vypocet v A. Dokazte, ze bezkontextovy jazyk L je jednoznacny prave vtedy ak existuje jednoznacny zasobnikovy automat A taky, ze L = L(A).

Uloha 4 (prez.)

Pre dany TM M nech L_M = { u#v^R | u, v su konfiguracie v A a zaroven u |- v }. Dokazte, ze L_M je bezkontextovy.

Uloha 5 (prez)

Nech je dane n a n-tica neprazdnych slov X v abecede {a,b}, X = (X₁,...,X_n). Uvazujme abecedu {a,b,#,1,2,..,n}.

Nech L(X) = { X_i1...X_ik#ik..i1 | i1,..ik \in {1,..n}, k>=0} Dokazte ze L(X) aj L(X)^c su bezkontextove.

Uloha 6

Dokazte, ze jazyk L={aⁱb^jc^k | neplati i=j=k}nie je deterministicky bezkontextovy jazyk.

Uloha 7 (odovzdavacia)

K danemu TM M a slovu w zostrojte TM M' taky, ze M' sa zastavi na vstupe \epsilon prave vtedy ak w \in L(M).