next up previous
Next: About this document ...

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?


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?


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?



 
next up previous
Next: About this document ...
Judit Csima
1999-12-02