Chomsky Hierarchy

Definition

The Chomsky hierarchy classifies a Formal Language based on the structure of its generating grammar or recognizing automaton.

1. Type 3: Regular Language (Finite Automaton)
2. Type 2: Context-Free Language (Pushdown Automaton)
3. Type 1: Context-Sensitive Language (Linear Bounded Automaton)
4. Type 0: Recursively Enumerable Language (Turing Machine)

Containment

Type 3 $\subset$ Type 2 $\subset$ Type 1 $\subset$ Type 0.