Home › GATE CSE › computerscience › Theory of Computation › Context-free languages are RECOGNISED by which t…
Context-free languages are RECOGNISED by which type of machine?
ADeterministic Finite Automata
BPushdown Automata (PDA) with stack memory
CLinear Bounded Automata
DTuring Machines only
Answer & Solution
Correct answer: B. Pushdown Automata (PDA) with stack memory
1. A PUSHDOWN AUTOMATON (PDA) is an NFA augmented with a STACK.
2. The stack lets the machine remember unbounded context (e.g. count matching parentheses).
3. CFL = NPDA: a language is context-free iff it is recognised by some non-deterministic pushdown automaton.
4. Hierarchy:
- Regular ⊊ Context-Free ⊊ Context-Sensitive ⊊ Recursively Enumerable
- DFA recognises Regular; PDA recognises CFL; LBA recognises CSL; TM recognises RE.
5. Option A is for regular languages only. Option C is for context-sensitive (stronger). Option D is too broad — Turing machines recognise CFLs too, but the SMALLEST class that EXACTLY recognises CFLs is PDAs.
_Source: Jeff Erickson, "Models of Computation", §5.4 (CFG and PDAs)._
Related questions
Which class of grammars generates ALL recursively enumerable languages?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?