[Overview] [Previous] [Next]

The Chomsky Hierarchy

The Chomsky hierarchy, as originally defined by Noam Chomsky, comprises four types of languages and their associated grammars and machines.

Language	Grammar	Machine	Example
Regular language	Regular grammar Right-linear grammar Left-linear grammar	Deterministic or nondeterministic finite-state acceptor	a*
Context-free language	Context-free grammar	Nondeterministic pushdown automaton	ab
Context-sensitive language	Context-sensitive grammar	Linear-bounded automaton	abc
Recursively enumerable language	Unrestricted grammar	Turing machine	Any computable function

These languages form a strict hierarchy; that is, regular languages context-free languages context-sensitive languages recursively enumerable languages.