index předchozí 1 2 3 4 5 6 7 8 9 10 11 12 následující

Cvičení jedenácté

Důkaz nerozhodnutelnosti redukcí

1) Je dán jazyk A {< M > | výpočet DTS M na epsilon je konečný}.

Dokažte, že A není rekurzivní. (Návod: PZ < A)
Je jazyk A rekurzivně spočetný?
Je komplement jazyka A rekurzivně spočetný?

2) Je dán jazyk A {< M > | M není úplný DTS}.

Dokažte, že A není rekurzivně spočetný. (Návod: co-PZ < A)
Dokažte, že ani komplement jazyka A není rekurzivně spočetný?

3) Binární relace R podmnožina {0,1}^* x {0,1}^* se nazývá rekurzivní právě když
     jazyk {x#y | (x,y) náleí R} je rekurzivní. Dokažte, že jazyk A podmnožina {0,1}^*
     je rekurzivně spočetný tehdy a jen tehdy, jestliže existuje binární relace R taková, že
     A={x náleží {0,1}^* | existuje y náleží {0,1}^* takové, že (x,y) náleží R}

4) Jiné nerozhodnutelné problémy viz skripta Věty 5.12, 5.13.      (DÚ)

5) Dokažte, že redukce je tranzitivní (viz skripta Věta 5.10). Je také symetrická?

6) Jsou dány jazyky A,B a platí A < B, B < A a jazyk A je rekurzivní. Jakého typu je jazyk B?