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 anbn
Context-sensitive language Context-sensitive grammar Linear-bounded automaton anbncn
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.