Chomsky Hierarchy

1 min read Updated Wed May 06 2026 17:34:33 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:
Type 3 $\subset$ Type 2 $\subset$ Type 1 $\subset$ Type 0.

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