410 !!!! Solutions (or Hints) to Chapter-end Exercises
TABLE A9.3 Transition Table for Exercise 9.11
Present state
Input symbol
0
1
b
qo
bRq,
bRqs
q,
ORq,
1Rq2
q2
1Lq3
1Rq2
bLq4
q3
OLQ3
1Lq3
bRqo
q4
OLq4
bLq4
ORQ6
Qs
bRQs
bRQs
bRQ6
®
Chapter 10
10.2 1. (B, w) is an input to M.
2. Convert B to an equivalent DFA A.
3. Run the Turing machine M j for A OFA on input (A, w)
4. If M j accepts, M accepts; otherwise M rejects
10.3 Construct a TM M as follows:
1. (A) is an input to M.
2. Mark the initial state of A (qo marked as q'6, a new symbol).
3. Repeat until no new states are marked: a new state is marked if
there is a transition from a state already marked to the new state.
4. If a final state is marked, M accepts (A); otherwise it rejects.
10.4 Let L = (T(A l ) - T(A 2 )) U (T(A 2 ) - T(A l )). L is regular and L = T(A').
Apply E OFA to (A').
10.8 Use Examples 10.4 and 10.5.
10.9 A TM is regarding a given Turing machine accepting an input, that is,
reaching an accepting state after scanning wand halting HALT TM is
regarding a given TM halting on an input (or M need not accept w in
this case).
10.10 Represent a number between 0 and 1 as 0 . Qj Q 2 .•. where Qj, Q2, •••
are binary digits. Assume the set to be a sequence, apply
diagonalization process and get a contradiction.
10.11 When a problem is undecidable, we can modify or take a particular case
of the problem and try for algorithms. Studying undecidable problems
may kindle an imagination to get better ideas on computation.
10.12 Suppose the problem is solvable. Then there is an algorithm to decide
whether a given terminal string w is in L. Let M be a TM. Then there
is a grammar G such that L(G) is the same as the set accepted by M.
Then w E L(G) if and only if M halts on w. This means that the halting
problem of TM is solvable, which is a contradiction. Hence the
recursiveness of a type 0 grammar is unsolvable.