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

V T*V or V T* 
V VT* or V T* 
Deterministic or nondeterministic finitestate acceptor  a* 
Contextfree language  Contextfree grammar  V (V T)*  Nondeterministic pushdown automaton  ab  
Contextsensitive language  Contextsensitive grammar  x y where x, y (V T)+, and x y 
Linearbounded automaton  abc  
Recursively enumerable language  Unrestricted grammar  (V T)+ (V T) *  Turing machine  Any computable function 
These languages form a strict hierarchy; that is, regular languages contextfree languages contextsensitive languages recursively enumerable languages.
Copyright © 1996 by David Matuszek
Last modified Apr 10, 1996