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 ).