[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 an timesbn times
Context-sensitive language Context-sensitive grammar Linear-bounded automaton an timesbn timescn times
Recursively enumerable language Unrestricted grammar 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