Chomsky Hierarchy
This describes an aspect of syntax, originally defined by Noam Chomsky, relating classes of languages with their corresponding grammars and machines:Language  Grammar  Machine  Example  Production Rules 

Regular language  Regular grammar

Deterministic or nondeterministic finitestate acceptor  a*  A > aB, A > a 
Contextfree language  Contextfree grammar  Nondeterministic pushdown automaton  a^{n}b^{n}  A > r 
Contextsensitive language  Contextsensitive grammar  Linearbounded automaton  a^{n}b^{n}c^{n}  _{A}A_{B} > _{A}r_{B} 
Recursively enumerable language  Unrestricted grammar  Turing machine  Any computable function  (No restrictions) 
These languages form a strict hierarchy, with greater expressive powers in the lower entries of the table.