Zostrojte zasobnikovy automat A pre jazyk
L = { ucv | u,v \in 1{0,1}* a zaroven u,v nie su binarne zapisy po sebe iducich cisel takych, ze u <= v a "c" je terminalny symbol}
Dokazte spravnost konstrukcie (t.j. L(A) = L).
Pozn.: 1{0,1}* reprezentuje mnozinu binarnych retazcov, zacinajucich bitom 1 (teda nemaju ziadne leading zeros).
Zadefinujte "1-ohraniceny" normalny tvar pre a-prekladace, taky, ze a-prekladac je "1-ohraniceny" ak moze citat a zapisovat najviac jeden znak, t.j. ak (q, u, v, p) \in M potom |u| <= 1 a |v| <= 1.
Dokazte ze trieda a-prekladacov je uzavreta na skladanie zobrazenia, teda ze pre kazde M1, M2 existuje M3, taky ze
M3(L) = M2(M1(L)).
Nech L je regularny jazyk. Pomocou nedeterministickych dvojsmernych konecnych automatov dokazte, ze jazyk
L' = { uv | existuje w z Sigma* : uvw je z L , |u|=|w|=|v| }
je regularny.
Zostrojte kontextovu gramatiku G pre jazyk
L = { wwRw | w \in {a,b}+ }
A dokazte spravnost svojej konstrukcie (t.j. L = L(G)).
Dokazte alebo vyvratte uzavretost Lcf na
a) zrkadlovy obraz
b) Kvocient
c) Shuffle
Pomocou zasobnikovych automatov dokazte uzavretost Lcf na substituciu.
Pozn.: Substitucia je zobrazenie t:\Sigma1* -> 2\Sigma2* take, ze t(x.y) = t(x).t(y). Trieda C je uzvreta na substituciu, ak pre vsetky L \in C, vsetky t, vsetky a \in \Sigma plati, ak t(a) \in C tak potom t(L) \in C.
Dokazte, ze jazyk L je bezkontextovy
L = { ww | w je z {a,b}* }C
Zostrojte kontextovu gramatiku G pre jazyk
L = { w | w \in {a,b,c}* take, ze #aw = #bw = #cw}
A dokazte spravnost svojej konstrukcie (t.j. L = L(G)).