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.

Context-Free Grammars and PDAs

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.

26 Qs · since 2011 · 41 marks · 1.6 marks/paperMedium yield

Take topic test

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… Guide

Type

GATE CSE 2026 Set 1Q25MSQ1 markMediumConsider the following grammar where $S$ is the start symbol, and $a$ and $b$ are terminal symbols. $S \rightarrow aSbS \mid bS \mid \epsilon$ Which of the following statements is/are true?
GATE CSE 2026 Set 1Q52MSQ2 marksMediumConsider the following context-free grammar $G$ . $S \to abaABAbba$ $A \to aaBBAb \mid bBabaa$ $B \to aBb \mid ab$ In the above grammar, $S$ is the start symbol, $a$ and $b$ are terminal symbols, and $A$ and $B$ are non-terminal symbols. Let $L(G)$ be the language generated by the grammar $G$ .…
GATE CSE 2026 Set 2Q29MSQ1 markEasyWhich of the following grammars is/are ambiguous?
GATE CSE 2026 Set 2Q48MSQ2 marksMediumLet $\Sigma = \{a, b, c, d\}$ and let $L = \{a^i b^j c^k d^\ell \mid i, j, k, \ell \ge 0\}$ . Which of the following constraints ensure(s) that the language $L$ is context-free?
GATE CSE 2025 Set 1Q19MCQ1 markEasyConsider the following context-free grammar $G$ , where $S$ , $A$ , and $B$ are the variables (non-terminals), $a$ and $b$ are the terminal symbols, $S$ is the start variable, and the rules of $G$ are described as: $S \rightarrow aaB \mid Abb$ $A \rightarrow a \mid aA$ $B \rightarrow b \mid bB$ …
GATE CSE 2025 Set 2Q24MCQ1 markEasyWhich ONE of the following languages is accepted by a deterministic pushdown automaton?
GATE CSE 2024 Set 1Q59NAT2 marksEasyLet $G = (V, \Sigma, S, P)$ be a context-free grammar in Chomsky Normal Form with $\Sigma = \{a, b, c\}$ and $V$ containing 10 variable symbols including the start symbol $S$ . The string $w = a^{30} b^{30} c^{30}$ is derivable from $S$ . The number of steps (application of rules) in the derivation $S \rightarrow^* w$ …
GATE CSE 2024 Set 2Q52MSQ2 marksMediumConsider a context-free grammar $G$ with the following 3 rules. $S \rightarrow aS, \; S \rightarrow aSbS, \; S \rightarrow c$ Let $w \in L(G)$ . Let $n_a(w)$ , $n_b(w)$ , $n_c(w)$ denote the number of times $a, b, c$ occur in $w$ , respectively. Which of the following statements is/are TRUE?
GATE CSE 2023Q39MCQ2 marksMediumConsider the context-free grammar $G$ below $\begin{aligned} S &\to aSb \mid X X &\to aX \mid Xb \mid a \mid b\text{ ,} \end{aligned}$ where $S$ and $X$ are non-terminals, and $a$ and $b$ are terminal symbols. The starting non-terminal is $S$ . Which one of the following statements is CORRECT?
GATE CSE 2023Q40MCQ2 marksMediumDiagramConsider the pushdown automaton (PDA) $P$ below, which runs on the input alphabet $\{a, b\}$ , has stack alphabet $\{\bot, A\}$ , and has three states $\{s, p, q\}$ , with $s$ being the start state. A transition from state $u$ to state $v$ , labelled $c/X/\gamma$ , where $c$ is an input symbol or $\epsilon$ …
GATE CSE 2022Q48MSQ2 marksMediumConsider the following languages: $L_1 = \{ww \mid w \in \{a,b\}^*\}$ $L_2 = \{a^n b^n c^m \mid m, n \ge 0\}$ $L_3 = \{a^m b^n c^n \mid m, n \ge 0\}$ Which of the following statements is/are FALSE?
GATE CSE 2021 Set 1Q1MCQ1 markMediumSuppose that $L_1$ is a regular language and $L_2$ is a context-free language. Which one of the following languages is NOT necessarily context-free?
GATE CSE 2021 Set 1Q51NAT2 marksMediumDiagramIn a pushdown automaton $P = (Q, \Sigma, \Gamma, \delta, q_0, F)$ , a transition of the form, where $p, q \in Q$ , $a \in \Sigma \cup \{\epsilon\}$ , and $X, Y \in \Gamma \cup \{\epsilon\}$ , represents $(q, Y) \in \delta(p, a, X).$ Consider the following pushdown automaton over the input alphabet $\Sigma = \{a, b\}$ …
GATE CSE 2020Q10MCQ1 markMediumConsider the language $L = \{a^n \mid n \ge 0\} \cup \{a^n b^n \mid n \ge 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?
GATE CSE 2017 Set 1Q10MCQ1 markMediumConsider the following context-free grammar over the alphabet $\Sigma = \{a, b, c\}$ with $S$ as the start symbol: $S \rightarrow abScT \mid abcT$ $T \rightarrow bT \mid b$ Which one of the following represents the language generated by the above grammar?
GATE CSE 2017 Set 1Q34MCQ2 marksEasyIf $G$ is a grammar with productions $S \rightarrow SaS \mid aSb \mid bSa \mid SS \mid \epsilon$ where $S$ is the start variable, then which one of the following strings is not generated by $G$ ?
GATE CSE 2017 Set 1Q37MCQ2 marksMediumConsider the context-free grammars over the alphabet $\{a,b,c\}$ given below. $S$ and $T$ are non-terminals. $G_1: S \to aSb | T, \ T \to cT | \epsilon$ $G_2: S \to bSa | T, \ T \to cT | \epsilon$ The language $L(G_1) \cap L(G_2)$ is
GATE CSE 2017 Set 2Q16MCQ1 markEasyIdentify the language generated by the following grammar, where $S$ is the start variable. $\begin{aligned} S &\to XY X &\to aX \mid a Y &\to aYb \mid \epsilon \end{aligned}$
GATE CSE 2016 Set 1Q16MCQ1 markEasyWhich of the following languages is generated by the given grammar? $S \longrightarrow aS \mid bS \mid \varepsilon$
GATE CSE 2016 Set 1Q42MCQ2 marksMediumConsider the following context-free grammars: $G_1: S \to aS | B, B \to b | bB$ $G_2: S \to aA | bB, A \to aA | B | \varepsilon, B \to bB | \varepsilon$ Which one of the following pairs of languages is generated by $G_1$ and $G_2$ , respectively?
GATE CSE 2016 Set 1Q43MCQ2 marksMediumDiagramConsider the transition diagram of a PDA given below with input alphabet $\Sigma = \{a,b\}$ and stack alphabet $\Gamma = \{X, Z\}$ . $Z$ is the initial stack symbol. Let $L$ denote the language accepted by the PDA. Which one of the following is TRUE?
GATE CSE 2016 Set 2Q17MCQ1 markEasyLanguage $L_1$ is defined by the grammar: $S_1 \to aS_1b \mid \varepsilon$ Language $L_2$ is defined by the grammar: $S_2 \to abS_2 \mid \varepsilon$ Consider the following statements: $P$ : $L_1$ is regular $Q$ : $L_2$ is regular Which one of the following is $\textbf{TRUE}$ ?
GATE CSE 2016 Set 2Q43MCQ2 marksEasyConsider the following languages: $L_1 = \{a^n b^m c^{n+m} : m, n \ge 1\}$ $L_2 = \{a^n b^n c^{2n} : n \ge 1\}$ Which one of the following is TRUE?
GATE CSE 2015 Set 1Q51MCQ2 marksMediumDiagramConsider the NPDA $(Q = \{q_0, q_1, q_2\}, \Sigma = \{0, 1\}, \Gamma = \{0, 1, \bot\}, \delta, q_0, \bot, F = \{q_2\})$ , where (as per usual convention) $Q$ is the set of states, $\Sigma$ is the input alphabet, $\Gamma$ is the stack alphabet, $\delta$ is the state transition function, $q_0$ is the initial…
GATE CSE 2015 Set 3Q32MCQ2 marksMediumWhich of the following languages are context-free? $L_1 = \{a^m b^n a^n b^m \mid m, n \ge 1\}$ $L_2 = \{a^m b^n a^m b^n \mid m, n \ge 1\}$ $L_3 = \{a^m b^n \mid m = 2n + 1\}$
GATE CSE 2011Q8MCQ1 markEasyWhich of the following pairs have DIFFERENT expressive power?

Topic guide

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.

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
common · MCQ · 1.5 marks · 2025, 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
common · mixed · 2 marks · 2026, 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
occasional · mixed · 2 marks · 2021, 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
occasional · MSQ · 1 marks · 2026
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
occasional · MSQ · 2 marks · 2026, 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
common · MCQ · 1 marks · 2025, 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
rare · NAT · 2 marks · 2024
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
occasional · MSQ · 2 marks · 2024
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
common · MCQ · 2 marks · 2023
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.

Context-Free Grammars and PDAs

26 Qs · since 2011 · 41 marks · 1.6 marks/paperMedium yield

Take topic test

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… Guide

Type

Topic guide

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

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
common · MCQ · 1.5 marks · 2025, 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
common · mixed · 2 marks · 2026, 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
occasional · mixed · 2 marks · 2021, 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
occasional · MSQ · 1 marks · 2026
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
occasional · MSQ · 2 marks · 2026, 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
common · MCQ · 1 marks · 2025, 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
rare · NAT · 2 marks · 2024
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
occasional · MSQ · 2 marks · 2024
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
common · MCQ · 2 marks · 2023
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