Algoritmuselmélet pótgyakorlat a hatodik gyakorlathoz 1. Bizonyítsuk be, hogy az Ld diagonális nyelv komplementer nyelve rekurzíve felsorolható, azaz $I^*\setminus L_d\in R{\cal E}\;$! 2. Legyenek L1 és L2 rekurzíve felsorolható nyelvek. Igaz-e, hogy $L_1\setminus L_2$ (vagyis azon szavak összessége, melyek L1-ben vannak, de nincsenek L2-ben) rekurzíve felsorolható? 3. Tekintsük a következő L nyelvet: $L=\{ x\in I^*;$ az Mx 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? Megoldások