[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 Production Type Machine Example
Regular language Regular grammar
  • Right-linear grammar
  • Left-linear grammar
V goes to T*V
or
V goes to T*
 V goes toVT*
or
V goes to T*		 Deterministic or nondeterministic finite-state acceptor a*
Context-free language Context-free grammar V goes to (V union T)* Nondeterministic pushdown automaton an timesbn times
Context-sensitive language Context-sensitive grammar x goes to y  where

x, y is a member of (V union T)+, and |x| <= |y|
or
αVβ goes to α(V union T)*β
where
α, β is a member of (V union T)*

 Linear-bounded automaton an timesbn timescn times
Recursively enumerable language Unrestricted grammar (V union T)+ goes to (V union T) * Turing machine Any computable function

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

Copyright © 1996 by David Matuszek
Last modified Apr 10, 1996