bounded automata is a proper subset of the context-sensitive languages.
To summarize, we have explored the relationships between several language
families and their associated automata. In doing so, we established a hierarchy of
languages and classified automata by their power as language accepters. Turing
machines are more powerful than linear bounded automata. These in turn are
more powerful than pushdown automata. At the bottom of the hierarchy are
finite accepters, with which we began our study.
EXERCISES
1. Collect examples given in this book that demonstrate that all the subset
relations depicted in Figure 11.4 are indeed proper ones.
2. Find two examples (excluding the one in Example 11.3) of languages that are
linear but not deterministic context-free.
3. Find two examples (excluding the one in Example 11.3) of languages that are
deterministic context-free but not linear.