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