581336 Laskennan teoria (syksy 2003) Harjoitus 1 (21.24.10.2003)

581336 Laskennan teoria (syksy 2003) Harjoitus 1 (21.24.10.2003)

1. Kuvaa luennolla esitetyn kielen{0ⁿ1ⁿ} tunnistavan Turingin koneen laskenta (ts. luettele ti- lanteet alkutilanteesta pysähtymiseen) syötteillä

(a) 000111 ja (b) 00111.

2. Esitä Turingin kone, joka tunnistaa kielen

{ww^R|w∈ {0,1}^∗},

missäw^Ron merkkijonowtakaperin.

3. Esitä Turingin kone, joka tunnistaa kielen

{w∈ {0,1}^∗|wsisältää yhtä monta nollaa ja ykköstä}.

4. Mikä onL(M)Turingin koneella

M = ({q₀, q₁, q₂, q₃},{0,1},{0,1, B}, δ, q₀, B,{q₃})

kun

(a) δ(q0,0) = (q1,1, R),δ(q1,1) = (q0,0, R)jaδ(q1, B) = (q3, B, R);

(b) δ(q0,0) = (q0, B, R),δ(q0,1) = (q1, B, R),δ(q1,1) = (q1, B, R)jaδ(q1, B) = (q3, B, R); sekä (c) δ(q0,0) = (q1,1, R),δ(q1,1) = (q2,0, L),δ(q2,1) = (q0,1, R)jaδ(q1, B) = (q3, B, R). Jos siirtymää ei ole merkitty, se on määrittelemätön.

5. Tarkastellaan oikealle etenevää Turingin konetta, joka on muuten kuin tavallinen Turingin kone, mutta kullakin askelella voi siirtää nauhapäätään yhden askelen oikealle tai pitää sen paikallaan.

Nauhapäätä siis ei voi siirtää vasemmalle. Millaisia kieliä voidaan tunnistaa oikealle etenevillä Turingin koneilla? (Vihje: tämän kieliluokan pitäisi olla tuttu Ohjelmoinnin ja laskennan perus- malleista.)