Chomsky Hierarchy

1 min read Last updated Wed Jun 10 2026 04:52:55 GMT+0000 (Coordinated Universal Time)

Four language classes, nested by expressive power.

Type	Language Class	Production Form	Accepting Device
3	Regular	$A \to aB$ , $A \to a$	Finite automaton
2	Context-free	$A \to \alpha$	Pushdown automaton
1	Context-sensitive	$\alpha \to \beta$ , $\lvert \beta \rvert \geq \lvert\alpha\rvert$ , $\alpha$ has non-terminal	Linear-bounded automaton
0	Recursively enumerable	$\alpha \to \beta$ , $\alpha$ has non-terminal	Turing machine

Each type is a subset of the below type.

\text{Type 3 }\subset\text{ Type 2 }\subset\text{ Type 1 }\subset\text{ Type 0}

Not all languages are RE. Proven using counting argument: $|\text{languages}| > |\text{TMs}|$ .

Was this helpful?