[Overview] [Previous] [Next]

Extending the Chomsky Hierarchy

We have discussed other types of languages besides those in the "classical" Chomsky hierarchy. For example, we noted that deterministic pushdown automata were less powerful than nondeterministic pushdown automata. Here is a table of some of the language classes we have covered that fit readily into this hierarchy.

Language Machine
Regular language Deterministic or nondeterministic finite-state acceptor
Deterministic context-free language Deterministic pushdown automaton
Context-free language Nondeterministic pushdown automaton
Context-sensitive language Linear-bounded automaton
Recursive language Turing machine that halts
Recursively enumerable language Turing machine

Not all language classes fit neatly into a hierarchy. For example, we have discussed the linear languages, which (like deterministic context-free languages) fit neatly between the regular languages and the context-free languages; however, there are languages that are linear but not deterministic context-free, and there are languages that are deterministic context-free but not linear.

In fact, mathematicians have defined dozens, maybe hundreds, of different classes of languages, and write papers on how these relate to one another. You should know at least the four "classic" categories that are taught in almost every textbook on the subject.

Copyright 1996 by David Matuszek
Last modified Apr 10, 1996