3. Sada domacich uloh

Uloha 1 (prez.)

Majme danu kontextovu gramatiku G. Zostrojte linearne ohraniceny automat (LBA) A, taky ze L(G) = L(A). Pri simulacii pouzite spatne odvodenie (teda postupne na paske robite spatne kroky az kym sa nedostanete ku \sigma).

Pri dokaze pouzite matematicku indukciu.

Uloha 2 (prez.)

Pomocou LBA (linearne ohranicenych automatov) dokazte uzavretost triedy kontextovych jazykov na inverzny homorfizmus. Teda, pre dany LBA A a homorfizmus h zostrojte LBA A', taky ze L(A') = h^-1(L(A)) = {w | h(w) \in L(A) }.

Uloha 3 (odovzdavacia)

Pre dany LBA A zostrojte LBA A', taky ze L(A') = {w^R | w \in L(A) }. Matematickou indukciou dokazte spravnost konstrukcie.

Uloha 4

Majme dany LBA A nad abecedou {a,b}. Zostrojte LBA A', taky ze L(A') = Shuffle(L(A), {c}^*). Zaroven nesmie A' pri simulacii menit policko na paske, na ktorom je symbol c.

Pozn.: {c}^* je jazyk vsetkych slov nad abecedou {c}.

Uloha 5

Zostrojte LBA A, taky ze L(A) = { aⁱ | kde i nie je prvocislo}

Uloha 6

Zostrojte LBA A, taky ze L(A) = { aⁱ | kde i je prvocislo}

Uloha 7

Formalne dokazte uzavretost L_csna operaciu Shuffle. Teda ak L₁, L₂ \in L_cs potom aj Shuffle(L₁, L₂) \in L_cs.

Uloha 8

Nech L je kontextovy jazyk. Pomocou LBA dokazte, ze jazyk

L' = { u | existuje v,w z Sigma^* : uvw je z L , |u|=|w|=|v| }

je kontextovy.

Uloha 9

Nech L je kontextovy jazyk. Pomocou LBA dokazte, ze jazyk

L' = { uw | existuje w z Sigma^* : uvw je z L , |u|=|w|=|v| }

je kontextovy.