(a) Replace every 1 by an x.
(b) Find the rightmost x and replace it with 1.
(c) Travel to the right end of the current nonblank region and create a
1 there.
(d) Repeat steps (b) and (c) until there are no more x’s.
The Transition function is given by
δ
δ
δ
( , ) ( , , ),
( , ) ( , , ),
( , ) ( , , )
q
q x R
q
q
L
q x
q R
0
0
0
1
1
2
1
1
=
=
=
¨
¨
,
( , ) ( , , ),
( , ) ( , , ),
( , ) ( , ,
δ
δ
δ
q
q R
q
q L
q
q L
2
2
2
1
1
1
1
1
1
1
1
=
=
=
¨
),
( , ) ( , , ).
δ q
q
R
1
3
¨
¨
=
where q 3 is the only final state.
Ì Exam ple 4.2.3: Design a Turing Machine that multiplies two positive
integers in unary notation.
Solu tion
Assume that the initial and final tape contents are to be as indicated in figure
above. Multiplication is visualized as a repeated copying of the multiplicand y
for each 1 in the multiplies x, whereby the string y is added the appropriate
number of times to the partially computed product. The steps involved in the
process are:
(i) Repeat the following steps until x contains no more 1’s—find a 1
in x and replace it with another symbol a. Replace the leftmost 0
by 0y.
(ii) Replace all a’s with 1’s.
Ì Exam ple 4.2.4: Design a Turing Machine that recognizes the set of bit
strings which have a 1 as their second bit i.e., the regular set
(
) (
)
*
0 1 1 0 1
∨
∨ .
Solu tion
We would like to have a Turing machine, which, starting at the leftmost
nonblank tape cell, moves right, and determines whether the second symbol is
194
Theory of Automata, Formal Languages and Computation
0 1
0
1 1 0 1 1 1
y
y
1
0
1
1 0 1 1 1
y
y
0 1 1 1
.........