Mathematical Foundation of Computer Science

DHARM

N-COM\CMS12-1.PM5

INTRODUCTION TO TURNING MACHINE 343

That is, to shift the complete string β one cell right and to push a symbol ξ before β.
Here we assume that set of input string Σ = {a, b}.
Fig. 12.13 shows the transition diagram of the Turing machine M from state q which
reaches to state p in finite steps and creates a blank space before string b that is replaced by an
extra symbol ξ and tape head move forward.

State Diagram

(X, B, R)

(, L)aa,

(, L)bb,

(,R)a, a

(B,a,L) (,L)b, b

(,L)a, a

(B,b,L)

(X,R)a,

(,XR)b,

q (, R)ba, (, R)ab,

(,R)b, b

(B, , R)

x

Fig. 12.13

A similar problem is occasionally facing, how to shift one cell left of the loaded

string on the tape i.e.

α q ξ β * α p β where α, β ∈ Γ* and p & q ∈ Q and ξ ∈{a, b}.

a a x b b B

a b

q

Þ a a b B

a b

p

b B

Fig. 12.14

Here machine is in state q and ready to read the string β′ where β′ = ξ b (a symbol

ξ and substring β) and in finite steps it reaches to state p and ready to read the remaining

string β.

Fig. 12.15 shows the state diagram of the Turing machine.

Following are the steps:

• Machine reads the first symbol ξ that is either symbol a or b. This cell should be
  blank. So create a blank space at this cell by replacing symbol a or b to B and move
  right.


• Skip all a’s and b’s so as reaches to blank.


• Replace the last symbol either a or b to blank and follow the move:


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