Deviata sada domacich uloh

Ulohy 3 a 7 su urcene na odovzdavanie a nie je mozne ich prezentovat. Odovzdavajte ich do STVRTKU 20. 4. rana (t.j. 8:10) do skatule na chodbe pred sekretariatom katedry informatiky.

Uloha 1

Zostrojte syntakticky riadenu prekladovu schemu, ktora prelozi aritmeticky vyraz (nad abecedou {+,-,*,(,),a,b} ) v infixovej notacii na ekvivalentny vyraz v prefixovej notacii. Demonstrujte na priklade:

 a*(a+b)-c*d

Uloha 2

Upravte algoritmus CYK (Cocke, Younger, Kasami) tak, aby pre kazde slovo, ktore patri do jazyka L(G) vyrobil strom odvodenia pre toto slovo.

Uloha 3

(*odovzdavacia uloha)
Dana je bezkontextova gramatika G = ({S,A,B,C},{a,b,c,d},P,S) s pravidlami:

S -> ASBS | C | epsilon
A -> aAb | epsilon
B -> cA | bB
C -> SdS

Pomocou algoritmu CYK zistite, ci slovo abcdab patri do L(G).

V ulohach 4-8 zistite, ci je dany problem rozhodnutelny. Svoje tvrdenie dokazte.

Uloha 4

Uvazujme TS, ktory moze zapisovat na pasku iba jeden znak 'a' (a nemoze zapisovat blank). Pre takyto stroj A a dane slovo w rozhodnut ci A akceptuje w.

Uloha 5

Zistit, ci pre dane dva bezkontextove jazyky L₁, L₂ (dane gramatikami) plati, ze L₁ je podmnozinou L₂.

Uloha 6

Zistit, ci pre dane dva regularne jazyky L₁, L₂ (dane gramatikami) plati, ze L₁ je podmnozinou L₂.

Uloha 7

(*odovzdavacia uloha)
Pre danu kontextovu gramatiku G rozhodnut, ci L(G) je bezkontextovy jazyk.

Uloha 8

Pre danu bezkontextovu gramatiku rozhodnut, ci je jednoznacna.