581336 Laskennan teoria (kevät 2006) Harjoitus 1, ratkaisuja

581336 Laskennan teoria (kevät 2006) Harjoitus 1, ratkaisuja

1. (a) Syöte 0011:

q₀0011 ` Xq<sub>1</sub>011 ` X0q₁11 ` Xq<sub>2</sub>0Y 1 ` q₂X0Y 1 ` Xq₀0Y 1

` XXq1Y 1 ` XXY q11 ` XXY q11 ` XXq2Y Y ` Xq2XY Y

` XXq0Y Y ` XXY q3Y ` XXY Y q3 ` XXY Y #q4

Laskenta pysähtyy, koska tilasta q4 ei ole siirtymää tyhjämerkillä (eikä olisi millään muul- lakaan). Koska q4 on hyväksyvä, merkkijono 0011 tulee hyväksytyksi.

(b) Syöte 001011:

q0001011 ` Xq101011 ` X0q11011 ` Xq20Y 011 ` q2X0Y 011

` Xq00Y 011 ` XXq1Y 011 ` XXY q1011 ` XXY 0q111

` XXY q20Y 1 ` XXq2Y 0Y 1 ` Xq2XY 0Y 1 ` XXq0Y 0Y 1

` XXY q30Y 1

Tilasta q3 ei ole siirtymää merkillä 0, joten laskenta pysähtyy. Tila q3 ei ole hyväksyvä, joten merkkijono 001011 ei tule hyväksytyksi.

2. Nauha-aakkosto on f a; b; A; B; # g, tyhjämerkki #. Tilojen nimet on jätetty merkitsemättä

a=A; R

b=B; R

B=B; L

#; #; L

#=#; R

a=a; R b=b:R

a=a; R b=b:R

a=a; L b=b:L

A=A; L B=B; L

#; #; L

a=A; L

b=B:L

A=A; L B=B; L A=A; L

A=A; R B=B; R

a=a; L

b=b:L

3. Olkoon M = (Q; ; ; ; q₀; B; F ) luennolla esitetyn määritelmän mukainen Turingin ko- ne. Muodostetaan tehtävässä annetun vaihtoehtoisen määritelmän mukainen kone M⁰ = (Q⁰; ; ; ⁰; q0; B; qyes; qno), missä qyes62 Q ja qno62 Q ja Q⁰ = Q [ f qyes; qnog. Siirtymäfunktio ⁰ määritellään seuraavasti:

⁰(qyes; X) ei ole määritelty millään X, ei myöskään ⁰(qno; X) jos q 2 Q ja (q; X) on määritelty, niin ⁰(q; X) = (q; X).

jos q 2 F ja (q; X) ei ole määritelty, niin ⁰(q; X) = (qyes; X; R).

jos q 2 Q F ja (q; X) ei ole määritelty, niin ⁰(q; X) = (q_no; X; R).

Selvästi millä tahansa syötteellä koneiden M ja M⁰ laskennat etenevät samalla lailla, kunnes M pysähtyy. Tällöin M⁰ tekee vielä yhden viimeisen askeleen, joko tilaan q_yes tai tilaan q_nosen mukaan pysähtyikö M hyväksyvään ja hylkäävään tilaan. Siis M ja M⁰ hyväksyvät ja hylkäävät tasan samat syötteet (ja siis myös jättävät pysähtymättä tasan samoilla syötteillä).

4. (Piirrä itse kaavioesitykset koneista.)

(a) Kone hyväksyy säännöllisen kielen 1(01), eli

L(M) = f w0w1w2: : : w2k 1w2kj w0= w2= : : : = w2k = 1; w1= w3= : : : = w2k 1= 0; k 0 g : (b) Kone hyväksyy säännöllisen kielen 011, eli

L(M) = f 0ⁿ1^mj n 0; m 1 g :

(c) Tarkastellaan, miten kone käyttäytyy tilanteessa uq₀w, missä u; w 2 f 0; 1 g. Jos w = 0, laskenta selvästi päättyy hyväksyvään tilaan. Jos w = 1w⁰tai w = 00w⁰jollain w⁰ 2 f 0; 1 g, laskenta selvästi päättyy hylkäävään tilaan. Muuten olkoon w = 01w⁰. Laskenta etenee

uq₀01w⁰ ` u1q<sub>1</sub>1w<sup>0</sup>` uq₂10w⁰` u1q₀0w⁰: Siis laskenta tilanteesta uq₀0v johtaa hyväksymiseen, jos joko

i. v = " tai

ii. v = 1w⁰, missä laskenta tilanteesta u1q00w⁰ johtaa hyväksymiseen.

Laskenta tilanteesta uq01v ei koskaan johda hyväksymiseen. Tästä nähdään helposti induk- tiolla, että laskenta tilanteesta uq00v johtaa hyväksymiseen, jos ja vain jos v = 1ⁿ jollain n 0. Valitsemalla erityisesti u = " nähdään, että

L(M) = f 01ⁿj n 0 g eli kone hyväksyy säännöllisen kielen 01.

2