alleryStart learning →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._
Keep practising Theory of Computation
Browse all Theory of Computation questions for GATE CSE, or explore more Computer Science topics.
Related questions
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$ isContext-free languages are RECOGNISED by which type of machine?A CFG is AMBIGUOUS ifConsider the CFG with rule $S \to aSb \mid \varepsilon$. The language generated isWhich of these is an example of an IRREGULAR (non-regular) language?