What are common examiner traps in Context-Free Grammars and PDAs?

Assuming CFLs are closed under complementation or intersection (forgetting L1 ∩ L2 can be non-CFL even if both are DCFLs). Confusing nested LIFO dependencies (context-free) with interleaved/cross-serial dependencies (non-context-free). Assuming DPDA and NPDA have equivalent expressive power (unlike DFA and NFA). Overlooking base conditions or -productions in CFGs, leading to off-by-one errors in terminal constraints (e.g., m > n vs m ≥ n, or n ≥ 0 vs n ≥ 1). Missing non-deterministic transitions in PDA diagrams where stack symbols are read without being altered (Z → Z). Forgetting that deriving is not counted by 2n-1 in CNF without special start symbol handling. Confusing non-strict inequalities (≥) with strict inequalities (>), which fail on the minimal base strings (e.g., w = c yielding na = 0, nb = 0, violating na > nb). Forgetting the initial start symbol count (+1) when balancing non-terminal net changes. Assuming linear relationships based only on a subset of derivation paths rather than universal derivation invariants. Overlooking initial requirements to read a symbol from the bottom stack marker (e.g., missing m ≥ 1). Confusing strict inequality (n < m) with non-strict inequality (n ≤ m) by failing to count stack symbols consumed during -transitions to the emptying state. Assuming acceptance requires a final state when acceptance by empty stack is explicitly specified.

GATE CSE Context-Free Grammars and PDAs PYQs

Q: What does GATE test in Context-Free Grammars and PDAs?

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.

Medium yield22.8% of Theory of Computation

Context-Free Grammars (CFG) and Pushdown Automata (PDA) form a cornerstone of the GATE CS Theory of Computation syllabus. Questions systematically test the boun… Read the guide

Take topic test

Questions: 26
Asked: since 2011
Total marks: 41
Marks / paper: 1.6

26 GATE CSE Context-Free Grammars and PDAs PYQs with solutions, from Theory of Computation. Browse all GATE CSE PYQs.

Questions

Every official paper that asked this topic, newest first.

What GATE tests in Context-Free Grammars and PDAs

Concepts, patterns, formulas and traps distilled from past papers.

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.

Core concepts

Deterministic Pushdown Automata (DPDA) vs Non-Deterministic Pushdown Automata (NPDA)
Deterministic Context-Free Languages (DCFL) and strict inclusion: Regular ⊂ DCFL ⊂ CFL
Single stack mechanics: nested comparisons (ai bj cj di) vs cross-serial non-CFL dependencies (ai bj ci dj)
Closure properties of CFLs and DCFLs (closure under regular intersection, non-closure under general intersection and complement)
Grammar ambiguity, leftmost/rightmost derivations, and parse trees
Chomsky Normal Form (CNF) structural derivation step counting
LL(k) lookahead limitations on DCFLs vs unambiguous CFGs
PDA acceptance modes (final state vs empty stack) and -transitions
Context-free grammar derivations and language generation
Net non-terminal balance in complete derivations
Counting arguments over terminal occurrences
Boundary cases and minimal-length string counterexamples
Pushdown Automata (PDA) transition diagrams and formal definitions
Stack operations (push, pop, replace/noop)
Acceptance by empty stack vs. acceptance by final state
Epsilon transitions and stack-emptying loops
Deriving language relations and inequalities (e.g., am bn where n < m, m ≥ 1)

Recurring question patterns

Language Identification from CFG
CommonMCQ1.5 marks2025, 2023, 2017, 2016
Given a CFG with recursive and non-recursive productions, determine the exact regular expression or set-builder notation of the language generated.
CFL vs. DCFL vs. Non-CFL Language Classification
Commonmixed2 marks2026, 2022, 2020, 2016
Given multiple parameterized languages (e.g., $a^i b^j c^k d^\ell$ with linear constraints or $w w^R$ variations), identify which are Context-Free, Deterministic Context-Free, or non-Context-Free based on single-stack LIFO nesting versus cross-serial dependencies.
PDA State Transition & Execution Tracing
Occasionalmixed2 marks2021, 2016, 2015
Given a formal 6/7-tuple or transition diagram of an NPDA/DPDA, analyze stack operations (push/pop/noop) to find accepting suffixes or count the number of accepted strings of fixed length.
Grammar Ambiguity and Derivation Counting
OccasionalMSQ1 marks2026
Determine if a grammar is ambiguous by finding multiple distinct parse trees/leftmost derivations for a short test string, or count unique rightmost derivations.
Grammar Invariants and Terminal Inequalities
OccasionalMSQ2 marks2026, 2017
Analyze productions to establish mathematical invariants over the number of generated terminals (e.g., bounds on $n_a(w)$ vs. $n_b(w)$ ).
Closure Properties and Expressive Power Hierarchy
CommonMCQ1 marks2025, 2022, 2021, 2011
Evaluate truth values of statements involving closure under intersection with regular sets, complementation, difference, or relative power of DPDA vs. NPDA vs. DFA/NFA.
Chomsky Normal Form (CNF) Derivations
RareNAT2 marks2024
Compute the exact number of derivation steps required to generate a terminal string of given length using a grammar in CNF.
Terminal Count Invariants via Derivation Rule Balance
OccasionalMSQ2 marks2024
Given a CFG, determine which equality or inequality relations over terminal counts (e.g., $n_a(w), n_b(w), n_c(w)$ ) hold for all words $w \in L(G)$ by setting up linear equations over production rule application counts.
PDA Language Identification via State and Stack Tracing
CommonMCQ2 marks2023
Given a formal transition diagram or definition of a PDA (with transition format $c/X/\gamma$ ), trace state transitions, push/pop actions, and non-deterministic or $\epsilon$ -transitions to deduce the exact set of accepted strings under a specified acceptance criterion (e.g., acceptance by empty stack).

Formulas GATE uses

Derivation Steps in Chomsky Normal Form (CNF)

\text{Total Steps} = 2n - 1

Used to find the exact number of derivation steps to generate any terminal string of length $n = |w|$ from a CFG in CNF ( $n-1$ binary rule applications and $n$ terminal rule applications).

CFL Set Difference Identity

L_1 - L_2 = L_1 \cap \overline{L_2}

Used when reasoning about why $L_{\text{reg}} - L_{\text{cfl}}$ is not necessarily context-free, as CFLs are not closed under complementation.

PDA Stack Balance Invariant

n_A(\text{stack}) = n_a(\text{pushed}) - n_b(\text{popped})

Used to compute acceptance conditions on input lengths (e.g., $n > m$ with total length $n + m = K$ yielding valid range for $m$ ).

Non-terminal Conservation Law

\text{Initial Non-terminals} + \sum_{i} k_i \cdot \Delta NT_i = 0

Used to establish linear relations between production rule application counts $k_i$ , where $\Delta NT_i$ is the net change in non-terminals produced by rule $i$ .

Terminal Count Accumulation

n_x(w) = \sum_{i} k_i \cdot \text{count}(x, \text{RHS}_i)

Used to express the total count of terminal symbol $x$ in word $w$ in terms of the number of times each production rule is applied.

PDA Transition Notation

\delta(u, c, X) = (v, \gamma)

Used to describe moving from state $u$ to $v$ upon reading input symbol $c \in \Sigma \cup \{\epsilon\}$ with top stack symbol $X$ , replacing $X$ with string $\gamma$ .

Language Acceptance by Empty Stack

N(P) = \{w \in \Sigma^* \mid (s, w, z_0) \vdash^* (q, \epsilon, \epsilon) \text{ for some } q \in Q\}

Used when the PDA accepts a word precisely when the stack becomes completely empty after processing the input.

Examiner traps in Context-Free Grammars and PDAs

Assuming CFLs are closed under complementation or intersection (forgetting L1 ∩ L2 can be non-CFL even if both are DCFLs).
Confusing nested LIFO dependencies (context-free) with interleaved/cross-serial dependencies (non-context-free).
Assuming DPDA and NPDA have equivalent expressive power (unlike DFA and NFA).
Overlooking base conditions or -productions in CFGs, leading to off-by-one errors in terminal constraints (e.g., m > n vs m ≥ n, or n ≥ 0 vs n ≥ 1).
Missing non-deterministic transitions in PDA diagrams where stack symbols are read without being altered (Z → Z).
Forgetting that deriving is not counted by 2n-1 in CNF without special start symbol handling.
Confusing non-strict inequalities (≥) with strict inequalities (>), which fail on the minimal base strings (e.g., w = c yielding na = 0, nb = 0, violating na > nb).
Forgetting the initial start symbol count (+1) when balancing non-terminal net changes.
Assuming linear relationships based only on a subset of derivation paths rather than universal derivation invariants.
Overlooking initial requirements to read a symbol from the bottom stack marker (e.g., missing m ≥ 1).
Confusing strict inequality (n < m) with non-strict inequality (n ≤ m) by failing to count stack symbols consumed during -transitions to the emptying state.
Assuming acceptance requires a final state when acceptance by empty stack is explicitly specified.

How questions are asked

Identify language expression generated by a CFG
Classify languages as Regular, DCFL, CFL, or non-CFL under given index constraints
Compute number of accepted strings of fixed length in a PDA (NAT)
Calculate derivation steps in CNF for a given string length (NAT)
Determine ambiguity and count distinct derivations for a test string (MSQ)
Find terminal ratio and inequality invariants of a grammar (MSQ)
Identify valid input suffix for PDA acceptance given prefix state
Symbol count relation verification (MSQ)
Algebraic derivation property testing
Identify language accepted by a given PDA transition diagram
Determine boundary constraints on symbol counts (m, n) accepted by a PDA

Paper trends

Shift from standard 1-mark classification MCQs to multi-select (MSQ) questions evaluating multiple language constraints simultaneously (e.g., nested vs cross-serial powers).
2026, 2022
Introduction of NAT questions involving exact combinatorial counting based on PDA stack dynamics or grammar normal form derivations.
2024, 2021
Increased focus on structural invariants of non-terminals (proving ratio bounds on terminal counts across recursive branches).
2026, 2017
Shift toward multi-select questions (MSQ) testing invariant terminal-count relations and boundary-case validation (e.g., base derivation strings disproving strict inequalities).
2024
Recent questions emphasize rigorous boundary condition checking (e.g., strictly $n < m$ vs $n \le m$ , and $m \ge 1$ vs $m \ge 0$ ) via $\epsilon$ -transitions requiring stack symbol consumption for empty-stack acceptance.
2023

Difficulty notes

Easy: Direct language generation of linear/simple CFGs, standard closure definitions, or basic hierarchy questions (DPDA vs NPDA). Medium: Multi-variable linear constraints on index tuples ( $i, j, k, \ell$ ), PDA state-stack tracing with non-deterministic transitions, proving grammar invariants via induction on derivation rules, and MSQs requiring counterexamples for non-CFL/ambiguity claims.