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

Deterministic or nondeterministic finitestate acceptor  a* 
Contextfree language  Contextfree grammar  Nondeterministic pushdown automaton  ab 
Contextsensitive language  Contextsensitive grammar  Linearbounded automaton  abc 
Recursively enumerable language  Unrestricted grammar  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