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