The Chomsky Hierarchy

Type 0

Formal Language for any Grammar .

Type 1

Formal Language for noncontracting Grammar . Noncontracting Formal Language

Type 2

Formal Language for context free Grammar . Context-Free Formal Language

Type 3

Formal Language for regular Grammar . Regular Formal Language

Example

is context-free, not regular.

Proof

It is context-free with rewrite rules and which produce . It is not regular. Suppose it is. Then it satisfies Regular Pumping Lemma. But clearly it doesn’t.