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.