581336 Laskennan teoria (syksy 2003) Harjoitus 2 (28.31.10.2003)

(1)

581336 Laskennan teoria (syksy 2003) Harjoitus 2 (28.31.10.2003)

1. Esitä kummallekin seuraavista kielistä sen tunnistava kaksinauhainen Turingin kone. Laadi kone siten, että se tekee mahdollisimman vähän siirtymiä.

(a) {0ⁿ1ⁿ|n≥0}

(b) {w:w^T|w∈ {0,1}^∗} missäw^T on merkkijonowtakaperin (aakkostona siis{0,1,:}) 2. Esitä yksinauhainen Turingin kone joka laskee funktionf:N→N, missäf(x) =x+ 1.

Funktionf laskeminen tarkoittaa tässä, että jos syötteenä on luonnollisen luvunxbinääriesitys, niin kone pysähtyy hyväksyvään tilaan ja tällöin nauhalla on luvun f(x) binääriesitys (ja sen lisäksi vain tyhjää). Binääriesityksessä merkitsevin bitti kirjoitetaan vasemmalle.

3. Esitä yksinauhainen epädeterministinen Turingin kone, joka tunnistaa kielen {wvw|v, w∈ {0,1}^∗,|w| ≥1}.

4. Muodostukoon kieli A aakkoston {0,1,:} merkkijonoista : w₁ : w₂ : · · · : w_n : missä w_i ∈ {0,1}^∗ kaikilla ija ainakin yhdellä indeksillä j pätee, ettäw_j on luvunj binääriesitys. Kuvaa pääpiirteissään (siis ei tilasiirtymäkaaviona) kielen A tunnistava epädeterministinen Turingin kone. Voit käyttää useita nauhoja, jos haluat.

5. Esitä rajoittamaton kielioppi, joka tuottaa kielen

{0ⁱ1^j2^k|0≤i≤j≤k}.

581336 Laskennan teoria (syksy 2003) Harjoitus 2 (28.31.10.2003)

581336 Laskennan teoria (syksy 2003) Harjoitus 2 (28.31.10.2003)

581336 Laskennan teoria (syksy 2003) Harjoitus 2 (28.31.10.2003)