Mathematical Foundation of Computer Science

DHARM

N-COM\CMS12-1.PM5

INTRODUCTION TO TURNING MACHINE 341

• The first symbol a is replaced by X (we count one a); skip all a’s and reaches to last b;
  replace it by a (now we have counted 2a’s); Corresponding to it last 2a’s converted to
  blank,
  a/ aabbb/ aa/ a/
  X aabbaaBB


• Repeat the previous step for next starting symbol a and so on we get
  Xa/ abb/ a/ a/ B B and similarly X Xa/ b/ aBBBB
  XXabaBBBB ⇒ XXXa/ a/ BBBB
  ⇒ XXXBBBBBB


• Therefore, the string is accepted (counted successfully ) if and only if the machine
  returns the string of tape symbols X’s followed by B’s (blank).
  Transition function (∂)

Assume Turing machine M = ({q 1 , q 2 , q 3 , q 4 , q 5 , q 6 , q 7 , q 8 }, {a, b}, {a, b, X, B}, B, q 0 , ∂, {q 8 }) where
δ’s are follows,
•δ(q 0 , a) = (q 1 , X, R)
•δ(q 1 , a) = (q 1 , a, R) // skip all a’s and reaches to first symbol b
•δ(q 1 , b) = (q 2 , b, R) // b remain b and move right
•δ(q 2 , b) = (q 2 , b, R) // skip all b’s and reaches to first a
•δ(q 2 , a) = (q 3 , a, L) // reaches to last b
•δ(q 3 , b) = (q 4 , a, R) // replace last b by a
•δ(q 4 , a) = (q 4 , a, R) // skip all a’s and move right so it reaches to blank
•δ(q 4 , B) = (q 5 , B, L) // reaches to last a
•δ(q 5 , a) = (q 6 , B, L) // replace it by Blank and move left
•δ(q 6 , a) = (q 7 , B, L) // replace one more a by Blank and move left
•δ(q 7 , a) = (q 7 , a, L) and δ(q 7 , b) = (q 7 , b, L) // skip all a’s and b’s and reaches to X
•δ(q 7 , X) = (q 0 , X, R) // X remain X and ready for next iteration and so on it reaches to
symbol blank
•δ(q 0 , B) = (q 8 , B, R) // if no more input symbol left so machine halts or terminates
successfully.
State Diagram

q 0 q 1

q 8

( , X, R)a ( , Y, L)b q

2

(B, B, R)

(, ,R)aa

(X, X, R)

(, ,L)aa

(Y, Y, L)

( , Y, L)b q

3

( , Y, L)b q

4

(, ,R)aa

q 5

(B, B, L)

q 7 q 6

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

(, ,L)aa

(, ,L)bb

Fig. 12.10