A nondeterministic Turing machine M is said to decide a language L if, for
all w ∈ Σ*, there is a path that leads either to acceptance or rejection.
EXERCISES
1. Discuss in detail the simulation of a nondeterministic Turing machine by a
deterministic one. Indicate explicitly how new machines are created, how
active machines are identified, and how machines that halt are removed from
further consideration.
2. Show how a two-dimensional nondeterministic Turing machine can be
simulated by a deterministic machine.
3. Write a program for a nondeterministic Turing machine that accepts the
language
L = {ww : w ∈{a,b} + }.
Contrast this with a deterministic solution.
4. Outline how one would write a program for a nondeterministic Turing
machine to accept the language
L = {ww R w : w ∈{a,b} + }.
5. Write a simple program for a nondeterministic Turing machine that accepts
the language
L = { xww R y : x,y,w ∈{a, b} + ,|x| ≥ |y|}.
How would you solve this problem deterministically?
6. Design a nondeterministic Turing machine that accepts the language
L = {a n : n is not a prime number}.
7. A two-stack automaton is a nondeterministic pushdown automaton with two
independent stacks. To define such an automaton, we modify Definition 7.1