Home › GATE CSE › computerscience › Theory of Computation › Which class of grammars generates ALL recursivel…
Which class of grammars generates ALL recursively enumerable languages?
ARegular grammars
BContext-free grammars
CContext-sensitive grammars
DUnrestricted (Type-0) grammars
Answer & Solution
Correct answer: D. Unrestricted (Type-0) grammars
1. CHOMSKY HIERARCHY (1956):
- Type 0: UNRESTRICTED — generates RE languages (recognised by Turing machines).
- Type 1: CONTEXT-SENSITIVE — generates CSL (recognised by LBA).
- Type 2: CONTEXT-FREE — generates CFL (recognised by PDA).
- Type 3: REGULAR (right-linear) — generates regular languages (recognised by DFA).
2. Strict inclusion: Type 3 ⊊ Type 2 ⊊ Type 1 ⊊ Type 0.
3. So Type 0 (unrestricted) is the MOST POWERFUL grammar class — generates EVERY RE language.
4. The trade-off: many decision problems are UNDECIDABLE for Type 0 grammars.
5. Other options give weaker classes.
_Source: Jeff Erickson, "Models of Computation", §6 (Chomsky Hierarchy intro) + cross-reference §5._
Related questions
What is a LEFTMOST DERIVATION?Which of the following languages is CONTEXT-FREE?Consider the grammar $S \to (S) \mid SS \mid \varepsilon$. The language generated isEvery regular language is also context-free. The PROOF construction isThe CYK algorithm parses a CFG in CNF. Its time complexity for a string of length $n$ isA LEFT-RECURSIVE rule in a CFG has the form $A \to A\alpha$ for some non-empty $\alpha$. WContext-free languages are CLOSED under which of the following operations?Is the language $L = \{a^n b^n c^n \mid n \geq 0\}$ context-free?