Algoritmuselmélet pótgyakorlat a hatodik gyakorlathoz

1. Bizonyítsuk be, hogy az L_d diagonális nyelv komplementer nyelve rekurzíve felsorolható, azaz $I^*\setminus L_d\in R{\cal E}\;$!

2. Legyenek L₁ és L₂ rekurzíve felsorolható nyelvek. Igaz-e, hogy $L_1\setminus L_2$ (vagyis azon szavak összessége, melyek L₁-ben vannak, de nincsenek L₂-ben) rekurzíve felsorolható?

3. Tekintsük a következő L nyelvet:
$L=\{ x\in I^*;$ az M_x egyszalagos TG létezik és semelyik $y\in I^*$ szóval mint inputtal elindítva sem mozdul el a fej a szalag első mezejéről $\}$.
Igazoljuk, hogy $L\in R$!

4. Legyen $f:\{ 0,1 \} ^*\rightarrow \{ 0,1\} ^*$ egy függvény, és tegyük fel, hogy a párokból álló $\{ x\char93 f(x),~~x\in \{ 0,1\} ^*\}$ nyelv rekurzíve felsorolható. Igaz-e, hogy ekkor f egy rekurzív függvény?

Algoritmuselmélet pótgyakorlat a hatodik gyakorlathoz

1. Bizonyítsuk be, hogy az L_d diagonális nyelv komplementer nyelve rekurzíve felsorolható, azaz $I^*\setminus L_d\in R{\cal E}\;$!

2. Legyenek L₁ és L₂ rekurzíve felsorolható nyelvek. Igaz-e, hogy $L_1\setminus L_2$ (vagyis azon szavak összessége, melyek L₁-ben vannak, de nincsenek L₂-ben) rekurzíve felsorolható?

3. Tekintsük a következő L nyelvet:
$L=\{ x\in I^*;$ az M_x egyszalagos TG létezik és semelyik $y\in I^*$ szóval mint inputtal elindítva sem mozdul el a fej a szalag első mezejéről $\}$.
Igazoljuk, hogy $L\in R$!

4. Legyen $f:\{ 0,1 \} ^*\rightarrow \{ 0,1\} ^*$ egy függvény, és tegyük fel, hogy a párokból álló $\{ x\char93 f(x),~~x\in \{ 0,1\} ^*\}$ nyelv rekurzíve felsorolható. Igaz-e, hogy ekkor f egy rekurzív függvény?

Algoritmuselmélet pótgyakorlat a hatodik gyakorlathoz

1. Bizonyítsuk be, hogy az L_d diagonális nyelv komplementer nyelve rekurzíve felsorolható, azaz $I^*\setminus L_d\in R{\cal E}\;$!

2. Legyenek L₁ és L₂ rekurzíve felsorolható nyelvek. Igaz-e, hogy $L_1\setminus L_2$ (vagyis azon szavak összessége, melyek L₁-ben vannak, de nincsenek L₂-ben) rekurzíve felsorolható?

3. Tekintsük a következő L nyelvet:
$L=\{ x\in I^*;$ az M_x egyszalagos TG létezik és semelyik $y\in I^*$ szóval mint inputtal elindítva sem mozdul el a fej a szalag első mezejéről $\}$.
Igazoljuk, hogy $L\in R$!

4. Legyen $f:\{ 0,1 \} ^*\rightarrow \{ 0,1\} ^*$ egy függvény, és tegyük fel, hogy a párokból álló $\{ x\char93 f(x),~~x\in \{ 0,1\} ^*\}$ nyelv rekurzíve felsorolható. Igaz-e, hogy ekkor f egy rekurzív függvény?