time proportional to the length of the input. Therefore,
L REG ⊆ DTIME (n).
But DTIME (n) includes much more than L REG . We have already established in
Example 13.7 that the context-free language {a n b n : n ≥ 0} can be recognized by
a two-tape machine in time O (n). The argument given there can be used for
even more complicated languages.
Example 14.4
The non-context-free language L = {ww : w ∈ {a,b}*} is in NTIME (n). This is
straightforward, as we can recognize strings in this language by the following
algorithm:
1. Copy the input from the input file to tape 1. Nondeterministically guess the
middle of this string.
2. Copy the second part to tape 2.
3. Compare the symbols on tape 1 and tape 2 one by one.
Clearly, all of the steps can be done in O (|w|) time, so L ∈ NTIME(n).
Actually, we can show that L ∈ DTIME(n) if we can devise an algorithm for
finding the middle of a string in O (n) time. This can be done: We look at each
symbol on tape 1, keeping a count on tape 2, but counting only every second
symbol. We leave the details as an exercise.
Example 14.5
It follows from Example 12.8 that
L CF ⊆ DTIME (n 3 )
and
L CF ⊆ NTIME (n).