efficiency, significant distinctions appear quickly. Here are two examples that
give us a first look at these issues.
Example 12.7
In Example 9.7 we constructed a single-tape Turing machine for the language
L = {a n b n : n ≥ 1}.
A look at that algorithm will show that for w = a n b n it takes roughly 2n steps to
match each a with the corresponding b. Therefore, the whole computation takes
O (n 2 ) moves.
But, as we later indicated in Example 10.1, with a two-tape machine we can
use a different algorithm. We first copy all the a's to the second tape, then match
them against the b's on the first. The situation before and after the copying is
shown in Figure 12.15. Both the copying and the matching can be done in O(n)
moves and is therefore much more efficient.
Figure 12.15
Example 12.8
In Sections 5.2 and 6.3 we discussed the membership problem for context-free
languages. If we take the length of the input string w as the problem size n, then
the exhaustive search takes O (n M ) steps, where M depends on the grammar. The
more efficient CYK algorithm requires an amount of work O(n 3 ). Both of these
algorithms are deterministic.
A nondeterministic algorithm for this problem proceeds by simply guessing