studied, although their relationships do not always have the neatly nested
structure of Figures 11.3 and 11.4. In some instances, the relationships are not
completely understood.
Example 11.3
We have previously introduced the context-free language
L = {w : n a (w) = n b (w)}
and shown that it is deterministic, but not linear. On the other hand, the language
L = {a n b n } ∪ {a n b 2n }
Figure 11.5
is linear, but not deterministic. This indicates that the relationship between
regular, linear, deterministic context-free, and nondeterministic context-free
languages is as shown in Figure 11.5.
There is still an unresolved issue. We introduced the concept of a
deterministic linear bounded automaton in Exercise 8, Section 10.5. We can now
ask the question we asked in connection with other automata: What role does
nondeterminism play here? Unfortunately, there is no easy answer. At this time,
it is not known whether the family of languages accepted by deterministic linear