Kazda uloha je za 10 bodov.
Dufam, ze som sa nepomylil pri prepisovani.

1. Najdite ekvivalentnu standardnu schemu, pricom pouzijete najviac 4 pomocne
premenne
begin
FI(y) <= if p(y) then f(g(y)) 
                 else h(FI(g(y)),g(y))
end [z]:=[FI(a)]

2. Uvazujme triedu strukturovanych schem. Je problem divergencie pre tuto
triedu rozhodnutelny (resp. ciastocne rozhodnutelny)?
Svoje tvrdenie zdovodnite.

3. Najdite ekvivalentnu volnu schemu
begin [y1,y2]:=[x,a]
1: if p(y2) then goto end
2: if q(y1) then goto 7
3: [y1,y2]:=[g(y1),f(y2)]
4: if p(y1) then goto 2
5: [y1]:=[f(y1)]
6: goto end
7: if p(y1) then goto 11
8: [y2]:=[f(y2)]
9: if q(y1) then goto 4
10: goto 7
11: [y1,y2]:=[f(y1),f(y2)]
12: if p(y2) then goto 5
13: [y2]:=[g(y2)]
14: goto 5
end [z]:=[y1]

4. Oznacme Z triedu tych standardnych schem, ktore sa zastavia. (t.j. Z={s
patri S; s sa zastavi}, V triedu volnych schem. Dokazte, ze Z je efektivne
prelozitelne do V (neformalne popiste prislusny algoritmus).