Jedenasta sada domacich uloh

Ak mate zaujem prezentovat ulohy starsieho data ako 3 sady dozadu, vyuzite nasledovny algoritmus:

1. pozri (na stranke), ci tu ulohu este nikto z Tvojho kruzku neprezentoval
2. ak nie, tak:
3. zvaz, ci nie je prilis lahka
4. ak mas pocit, ze nie je:
5. uisti sa v svojom presvedceni u svojho cviciaceho (napr. mejlom)
6. ak s Tebou suhlasi, prezentuj (a upovedom ostatnych z kruzku)

Vseobecne upozornenie: Ak bola odprednasana vseobecna konstrukcia na riesenie danej ulohy, pouzivajte ju.

Uloha 1

Dana je cast delta funkcie zasobnikoveho automatu. Podla konstrukcie z prednasky k nej zostrojte prislusnu cast ekvivalentnej bezkontextovej gramatiky.

d(q,a,A)=(q1,B)      d(q1,a,c)=(q2,BBC)   d(q1,b,B)=(q1,epsilon)
d(q,a,B)=(q1,BA)     d(q,a,Z)=(q1,ZB)     d(q,b,A)=(q2,epsilon)

V ulohach 2-5 dokazte, ze dane jazyky nie su bezkontextove:

Uloha 2

L = { aⁱb^jaⁱb^j | i,j > 0 }

Uloha 3

L = { aⁱb^jc^k | 0 <= i <= j <= k }

Uloha 4

L = { u | pocet a v u = pocet b v u = pocet c v u }
nad abecedou {a,b,c}

Uloha 5

L = { ww | w je nad abecedou {a,b,c} }

Uloha 6

Su bezkontextove jazyky uzavrete na komplement? Svoje tvrdenie zdovodnite.

Uloha 7

Nech L je bezkontextovy jazyk. Definujme L':
L' = { uv^R | uv patri do L }
Je nutne L' bezkontextovy?

Uloha 8

Dokazte alebo vyvratte: Pre kazdu bezkontextovu gramatiku G existuje konstanta p taka, ze pre kazde slovo w z L(G) existuje odvodenie, v ktorom sa v ziadnej vetnej forme nevyskytuje viac ako p neterminalov.

Uloha 9

Najdite jazyk, ktory splna podmienky pumpovacej lemy a nie je bezkontextovy.

Zaradte do Chomskeho hierarchie, kde L_r je lubovolny regularny jazyk a L_CF je lubovolny bezkontextovy jazyk.

Uloha 10

Kvocient L_r / L_CF.

Uloha 11

Kvocient L_CF / L_r.