Chomsky Hierarchy | Sahithyan's Notes

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 strict subset of the type below it.

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

Not all languages are RE. Proven by counting: $|\text{languages}| > |\text{TMs}|$ (languages are uncountable, TMs are countable).

Closure Properties

Operation	Regular	CFL	CSL	RE
Union	Yes	Yes	Yes	Yes
Concatenation	Yes	Yes	Yes	Yes
Kleene star	Yes	Yes	Yes	Yes
Intersection	Yes	No	Yes	Yes
Complement	Yes	No	Yes	No
Difference	Yes	No	Yes	No