Mathematical Foundation of Computer Science

DHARM

N-COM\CMS12-1.PM5

344 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

• r to p through t if β is a string of all b’s,


• r to p through s and t as required for mix strings.

State Diagram

(,L)a, a

(B,a,R)

(B,b,R)

(B,L)a,

(,BL)b,

(, L)ba, (, L)ab,

(,L)b, b

q

(,R)a, a

(,R)b, b

( , B, R)b

(B,B,L)

( , B, R)a

r

s

t

p

Fig. 12.15

Let us solve another problem of Turing machine. This problem states how to copying

the block (that is loaded the tape symbol string) i.e. if x is the string formed over symbols

{a, b} is loaded on the tape shown in the Fig. 12.14 then copy this string x s.t. the resulting

string is the string x followed by x. Now the tape contains the string (x + x).

x BB

x x BB

q

p

Fig. 12.16

A simple way to construct the Turing machine for copying the string by assuming that a

cell is blank before the string x so ID of the machine would be q B x * p B x B x

The state diagram of the Turing machine is shown in Fig. 12.17