Desiata sada domacich uloh
Ulohy 1 a 2 su urcene na odovzdavanie a nie je mozne ich prezentovat.
Odovzdavajte ich do stredy 1.12. rana (t.j. 8:10) do skatule na chodbe
pred sekretariatom katedry informatiky.
Vseobecne upozornenie: Ak bola odprednasana vseobecna konstrukcia na
riesenie danej ulohy, pouzivajte ju.
Uloha 1
(*odovzdavacia uloha)
Dana je bezkontextova gramatika
G = ({A,B,C,D},{a,b,c},P,A)
s pravidlami:
A -> DCa | Aa | ba
B -> BaB | Bb | Ac
C -> ADb
D -> ABCa
Standardnym postupom zostrojte ekvivalentnu gramatiku v Greibachovej tvare.
Uloha 2
(*odovzdavacia uloha)
Modifikacia zasobnikoveho automatu: automat s pruznou hlavou v zasobniku.
Automat moze v jednom kroku vybrat naraz viacero (najviac k>1)
symbolov.
Zadefinujte takyto modifikovany automat (standardne styri def.) a
porovnajte jeho vypoctovu silu so standardnym zasobnikovym automatom.
Svoje tvrdenie dokazte.
Uloha 3
Modifikacia zasobnikoveho automatu: automat, ktory moze v kazdom kroku vlozit
do zasobnika najviac jedno pismeno.
Porovnajte jeho vypoctovu silu so standardnym zasobnikovym automatom.
Svoje tvrdenie dokazte.
Uloha 4
Modifikacia zasobnikoveho automatu: zasobnikova abeceda je dvojznakova.
Porovnajte jeho vypoctovu silu so standardnym zasobnikovym automatom.
Svoje tvrdenie dokazte.
Uloha 5
Modifikacia zasobnikoveho automatu: zasobnikova abeceda je jednoznakova.
Porovnajte jeho vypoctovu silu so standardnym zasobnikovym automatom.
Svoje tvrdenie dokazte.
Uloha 6
Majme slovo w = a1a2 ... an.
Otocenim podslova aiai+1...aj z
neho dostaneme slovo
w' = a1...ai-1 aj aj-1 ... ai aj+1 ... an
Nech L je jazyk. Jazyk Otoc(L) je mnozina slov, ktore sa daju
zostrojit zo slov z jazyka L konecnym poctom operacii otocenia podslova.
Dokazte alebo vyvratte: trieda regularnych jazykov je uzavreta na operaciu Otoc.
Uloha 7
Je trieda bezkontextovych jazykov uzavreta na operaciu Shuffle?
(Definicia Shuffle vid. 8. sada.)
Zaradte nasledujuce jazyky do Chomskeho hierarchie (t.j. zistite, ci je
jazyk regularny, bezkontextovy alebo nie je bezkontextovy. Svoje tvrdenie
dokazte).
Uloha 8
L = { c u v | pocet a v u sa rovna poctu b vo v }
(nad abecedou {a,b,c})
Uloha 9
L = { u c v | pocet a v u sa rovna poctu b vo v }
(nad abecedou {a,b,c})
Uloha 10
L je generovany bezkontextovou gramatikou, pricom mnozina terminalov
je jednoprvkova.
Uloha 11
L = { u#v | u,v su zapisy cisel v dvojkovej sustave
pricom plati v = u + 7 }
(nad abecedou {0,1,#})
Uloha 12
L = { u#vR | u,v su zapisy cisel v dvojkovej sustave
pricom plati v = u + 7 }
(nad abecedou {0,1,#})
Uloha 13
L = { u#vR#w | u,v,w su zapisy cisel
v dvojkovej sustave pricom plati w = u+v }
(nad abecedou {0,1,#})