final state q f and the transitions
for all q ∈ F and a ∈ T.
Section 9.2
3. (a) We can think of the machine as constituted of two main parts, an addone machine that just adds one to the input, and a multiplier that
multiplies two numbers. Schematically they are combined in a simple
fashion.
5. (c) First, split the input into two equal parts. This can be done as
suggested in Exercise 10, Section 9.1. Then compare the two parts,
symbol by corresponding symbol until a mismatch is found.
8. A solution:
The state q 0 is any state in which the searchright instruction may be
applied.
Section 9.3
2. We have ignored the fact that a Turing machine, as defined so far, is
deterministic, while a pda can be nondeterministic. Therefore, we cannot yet
claim that Turing machines are more powerful than a pushdown automata.
Chapter 10