The Chomsky Hirarchy

THE CHOMSKY HIERARCHY: The Chomsky Hierarchy, as originally defined by Noam Chomsky, comprises four types of languages and their associated grammars and machines.

EXTENDING THE CHOMSKY HIERARCHY: So far we have discussed about other types of languages besides those in the “classical Chomsky hierarchy. For example, we noted that deterministic pushdown automaton were less powerful than nondeterministic pushdown automata. The table below shows a table of some of the language classes we have covered that fit readily into the hierarchy.

It should be noted that not all language classes fit into a hierarchy. When linear languages are considered, they 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.