5.1The Chomsky hierarchy
The idea
The Chomsky hierarchy lines up four grammar types with four machines, each strictly more powerful than the one before.
Think of it like this: Four tool kits: pocket knife (regular), Swiss army knife (context-free), workshop (context-sensitive), full factory (unrestricted).
Why it exists
Everything in TOC fits on this ladder, and many questions only ask where a language sits.
How it works
- Type 3 regular ↔ finite automaton.
- Type 2 context-free ↔ pushdown automaton.
- Type 1 context-sensitive ↔ linear bounded automaton.
- Type 0 unrestricted ↔ Turing machine (recursively enumerable).
Worked example: Where do these live?
(a+b)*ab: regular. aⁿbⁿ: DCFL. wwᴿ: CFL. aⁿbⁿcⁿ: CSL. A_TM: RE, not recursive.
Now play with it
- →Click each language and see the smallest class highlighted.
aⁿbⁿcⁿ: Two comparisons at once: not a CFL, but a linear-bounded automaton decides it.
Regular ⊂ DCFL ⊂ CFL ⊂ CSL ⊂ Recursive ⊂ RE. A language belongs to its class and to every larger class (green).
Check yourself
The class of languages accepted by linear bounded automata is
Exam notes (the dense version)
Type 3 regular ↔ finite automaton. Type 2 context-free ↔ PDA. Type 1 context-sensitive ↔ linear bounded automaton. Type 0 unrestricted ↔ Turing machine (RE). Each class properly contains the one before: Regular ⊂ DCFL ⊂ CFL ⊂ CSL ⊂ Recursive ⊂ RE.
Previous year questions: Language Hierarchy & Closure Tables (7)
PYQs are grouped by topic, so this is the full set for Language Hierarchy & Closure Tables; try the ones that match this subtopic. Open all 7 on the topic page.