The Chomsky Hierarchy is a hiearchy of classes of grammars. It is useful in showing what language a type of grammar can recognise. More powerful grammars contain less powerful ones, and thus can also recognise language recognised by the “inferior” grammars.

From most powerful to least powerful:

Recursively Enumerable (Type 0):

• Makes use of unrestricted rules. Both sides of each rule can have any number of terminal and non-terminal symbols.

• As expressive as Turing Machines.

• A B C -> D E

Context-Sensitive Grammar (Type 1):

• Right side of each rule must have at least as many symbols as the left side.

• As expressive as Linearly-Bounded Turing Machines.

• Can represent languages such as $$a^nb^nc^n$$.

• A X C -> A Y C

Context-Free Grammar (Type 2):

• The left side consists of a single non-terminal symbol.

• Equivalent to a pushdown (stack) automaton.

• Can represent languages such as $$a^nb^n$$.

Regular (Type 3):

• A non-terminal symbol on the left side, and a terminal (optionally followed by a non-terminal) symbol on the right hand side.

• Equivalent to finite-state automata.

• Can represent languages such as $$a^*b^*$$.