Next: About this document ...
Algoritmuselmélet gyakorlat (6)
1. Legyen M a következő Turing gép:
,
ahol
k=2,
,
,
,
,
áll |
1.sz. |
2.sz. |
1.sz |
|
2.sz |
|
új áll |
q0 |
0 |
ü |
0 |
H |
X |
J |
q1 |
|
1 |
ü |
1 |
H |
X |
J |
q1 |
|
ü |
ü |
ü |
H |
ü |
H |
q5 |
q1 |
0 |
ü |
0 |
J |
0 |
J |
q1 |
|
1 |
ü |
1 |
J |
1 |
J |
q1 |
|
ü |
ü |
ü |
H |
ü |
B |
q2 |
q2 |
ü |
0 |
ü |
H |
0 |
B |
q2 |
|
ü |
1 |
ü |
H |
1 |
B |
q2 |
|
ü |
X |
ü |
B |
X |
J |
q3 |
q3 |
0 |
0 |
0 |
H |
0 |
J |
q4 |
|
1 |
1 |
1 |
H |
1 |
J |
q4 |
q4 |
0 |
0 |
0 |
B |
0 |
H |
q3 |
|
0 |
1 |
0 |
B |
1 |
H |
q3 |
|
1 |
0 |
1 |
B |
0 |
H |
q3 |
|
1 |
1 |
1 |
B |
1 |
H |
q3 |
|
0 |
ü |
0 |
H |
ü |
H |
q5 |
|
1 |
ü |
1 |
H |
ü |
H |
q5 |
(a) Mi lesz a 2. szalagon a q2 állapotban?
(b) Mi LM, azaz milyen 0-1 -sorozatokat ismer fel M?
(c) Hogyan módosítható M, hogy a megfelelő 0-1 értékű
függvényt számolja ki?
2. Bizonyísuk be, hogy
!
3. Rekurzív-e a prímszámokból
(pl. bin. ábrázolás) álló nyelv?
4. Bizonyítsuk be, hogy:
rekurzív (rekurzíve felsorolható)
és az
(egymás után írás) nyelv rekurzív (r.f.).
5. Rekurzív-e az a nyelv, ami azon
szavakból áll, melyekre
létezik Mx (az x szóval kódolt Turing gép), Mx egyszalagos, és
a feje az y input
esetén a szalagján csak "jobbra" lépéseket tesz (sohasem teszi meg a
"helyben" illetve "balra" lépéseket)?
6. Álljon az L nyelv azon
párokból, melyekre az Mx
kétszalagos Turing gép létezik, és Mx az y input esetén
nem változtatja meg az első szalagjának a tartalmát (azaz
Mx futása során az első szalagján végig az
sorozat található)!
Bizonyítsuk be, hogy az L nyelv nem rekurzív!
7. Álljon L szópárokból:
.
Tegyük fel, hogy
L, mint egy
feletti nyelv rekurzíve felsorolható.
Bizonyítsuk be, hogy az
nyelv is rekurzíve felsorolható!
8. Mutassuk meg, hogy van olyan
függvény, ami nem
rekurzív, de amire a következő
függvény
rekurzív:
g(y)=1, ha f(y) páratlan és g(y)=0, ha f(y) páros!
Next: About this document ...
Judit Csima
1999-11-24