Mathematical Foundation of Computer Science

DHARM

N-COM\CMS12-1.PM5

INTRODUCTION TO TURNING MACHINE 349

tape cells contains (x + 1) 0’s corresponding to string x followed by a symbol 1 (breaker) and
next to it symbol blanks. Now our task is to copy this block of (x + 1) 0’s, y times.
Thus, Turing machine starts the computation over the string x and it copy the block
according to the state diagram shown in Fig. 12.24.

(0,0,R) (0,0,L)

(0,0,R)

(1,1,R) (B,0,L)

(1,1,L)

(0,X,R)

(0,0,L)

(X,X,R)

(1,1,R)

(0,B,L)

(0,0,R) HALT

q 0 q 6

q 0

q 1 q 2 q 3

q 4

Fig. 12.24

This state diagram will copy the string x once hence, repetition of this sequence y times

will compute the required result i.e., x* y.

EXERCISES

12.1 Construct the TM for the following languages over {0, 1}.

(i)L = {x/x contains the substring 000} (ii)L = {x/x is palindrome}

(iii)L = {w w/w ∈ {0, 1}*} (iv)L = {w wRev/w ∈ {0, 1}*}

(v)L = {w c wRev/w ∈ {0, 1}*} (vi)L = {w w w/w ∈ {0, 1}*}

12.2 Construct the TM for languages L 1 and L 2.

(i)L 1 = {0n 1 n 2 n/n ≥ 1} (ii)L 2 = {0n 1 n 2 n/n ≥ 0}

12.3 Construct the TM that computes the indicated functions (f : Nk → N), where x, y, z ∈ N.

(i)f(x) = x + 7 (ii)f(x) = x^3

(iii)f(x) = x mod 7(iv)f(x, y) = x^2 + xy

(v)f(x, y, z) = x + 2y + 3z (vi)f(x, y, z) = 2x + 3y + z^2

(vii)f(x) = smallest integer greater then or equal to log 2 (x + 1), i.e.,

f(0) = 0, f(1) = 1, f(2) = f(3) = 2, f(4) = ...= f(7) = 3, and so on.

12.4 Consider f 1 and f 2 are two natural functions that are computed by TMs M 1 and M 2 respectively.

Construct a TM that computes each of the following functions,

(i)f 1 + f 2 (ii)f 1 – f 2

(iii) mod (f 1 , f 2 )(iv) max (f 1 , f 2 )

(v) min (f 1 , f 2 ).