Theory of Computation · Context-Free Grammars and PDAs
Official IIT answer key · IIT Delhi · Audited Aug 2026
GATE CSE 2020 Q10 · MCQ · 1 mark
Key concept
No account needed
Sit 5 related Context-Free Grammars and PDAsPYQs as a guest. We'll score the set and show which traps cost marks — sign in only if you want to save the run.
Topic notes
Context-Free Grammars (CFG) and Pushdown Automata (PDA) form a cornerstone of the GATE CS Theory of Computation syllabus. Questions systematically test the boundary between Regular, DCFL, CFL, and non-CFL classes, structural invariants of grammars (ambiguity, terminal count ratios, derivation steps), and operational tracing of PDAs. Over recent years, the topic has expanded from standard single-choice language classifications to multi-select invariant verification and exact counting NAT questions.
Full Context-Free Grammars and PDAs guide →Consider the language L = \an n 0\ \an bn n 0\ and the following statements. I. L is deterministic context-free. II. L is context-free but not deterministic context-free. III. L is not LL(k) for any k. Which of the above statements is/are TRUE?
Topic-wise GATE CS PYQs with verified steps
Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.
