which sequence of productions is applied in the derivation of w. If we work with
a grammar that has no unit-or λ-productions, the length of the derivation is
essentially |w|, so we have an O (n) algorithm.
These examples suggest that efficiency questions are affected by the type of
Turing machine we use and that the issue of determinism versus nondeterminism
is a particularly crucial one. We will look at this in more detail in Chapter 14.
EXERCISES
1. Consider the language
L = {ww : w ∈ {a,b} + }.
Discuss the construction and efficiency of algorithms for accepting L on
(a) a standard Turing machine,
(b) on a two-tape deterministic Turing machine,
(c) on a single-tape nondeterministic Turing machine,
(d) on a two-tape nondeterministic Turing machine.
2. Repeat Exercise 1 for
L = {www : w ∈{a,b} + }.