2. Sada domacich uloh

Uloha 1 (prez.)

Dokazte ekvivalenciu Chomskeho definicie a standardnej definicie kontextovych gramatik (CSG).

Pre CSG s mnozinou terminalov T a mnozinou neterminalov N

Chomskeho definicia je, ze pravidla CSG maju tvar "u \alpha v -> u \beta v", kde u,v \in (N u T)^*, \alpha \in N, \beta \in (N u T)⁺
Standardna definicia je, ze pravidla CSG mju tvar "u -> v", kde u \in (N u T)^* N (N u T)^*, v \in (N u T)⁺ a zaroven |u| <= |v|

Uloha 2 (prez.)

Pomocou LBA (linearne ohranicenych automatov) dokazte uzavretost triedy kontextovych jazykov na zretazenie.

Uloha 3

Zostrojte LBA A pre jazyk

L = { u#v | u,v \in {0,1}^* a zaroven u,v su binarne zapisy po sebe iducich cisel takych, ze u <= v}

Dokazte spravnost konstrukcie (t.j. L(A) = L).

Uloha 4

Zostrojte LBA A pre jazyk

L = { a^{2ⁿ} | n>= 0 }

Dokazte spravnost konstrukcie (t.j. L(A) = L).

Pozn.: a^{2ⁿ} = a na dva na n-tu

Uloha 5

Zostrojte cast delta funkcie pre LBA, ktora nahradi nejake podslovo u=a₁...a_n, podslovom kratsim v=b₁..b_m, n>m.

Uloha 6

Zostrojte cast delta funkcie pre LBA, ktora transformuje slovo v \in {a,b,c}⁺ na u \in {a,b}^*c^* , tak ze h(u) = h(v), kde

h(a) = a

h(b) = b

h(c) = \epsilon

a #_cu = #_cv.

Teda inymi slovami, presunie vsetky c na koniec slova.

Uloha 7

Zostrojte LBA, taky ze bude lexikograficky generovat vsetky slova dlzky 1 az vekost vstupu (je to LBA, takze nema viac pasky ako dlzka vstupu) nad abecedou {a,b}.

Automat zacina v konfiguracii (q₀#...#) a postupne sa dostava do konfiguracii (q₀#...a), (q₀#...b), (q₀#...ab), (q₀#...bb), atd.