308 g Theory of Computer Science
8. For the TM given in Example 9.4:
(a) 011 is accepted by M
(b) 001 is accepted by M
(c) 00 is accepted by M
(d) 0011 is accepted by M.
9. For the TM given in Example 9.5:
(a) 1 is accepted by M
(b) 11 is accepted by M
(c) 111 is accepted by M
Cd) 11111 is accepted by M
10. In a standard TM (Q. 2:. r, 8. qQ, b. F) the blank symbol b is
(a) in 2: - r
(b) in r - 2:
(c) r Ii 2:
(d) none of these
EXERCISES
9.1 Draw the transition diagram of the Turing machine given in Table 9.1.
9.2 Represent the transition function of the Turing machine given in
Example 9.2 as a set of quintuples.
9.3 Construct the computation sequence for the input 1b11 for the Turing
machine given in Example 9.5.
9.4 Construct the computation sequence for stlings 1213, 2133. 312 for the
Turing machine given in Example 9.8.
9.5 Explain how a Turing machine can be considered as a computer of integer
functions (i.e. as one that can compute integer functions; we shall discuss
more about this in Chapter 11).
9.6 Design a Turing machine that converts a binary stling into its equivalent
unary string.
9.7 Construct a Turing machine that enumerates {Oil 1
11 1/1 2' : I}.
9.8 Construct a Turing machine that can accept the set of all even
palindromes over {O, I}.
9.9 Construct a Turing machine that can accept the strings over {O, I}
containing even number of l's.
9.10 Design a Turing machine to recognize the language {a''Y'c
ll1
In. m 2' : I}.
9.11 Design a Turing machine that can compute proper subtraction. i.e.
111 -'- II, where m and n are positive integers. m -'- n is defined as m - n
if In > J7 and 0 if m ::; /1.