alleryStart learning →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)._
Keep practising Theory of Computation
Browse all Theory of Computation questions for GATE CSE, or explore more Computer Science topics.
Related questions
Which class of grammars generates ALL recursively enumerable languages?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 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?