Pushdown Automata and CFG: Construction, Stack Traces and CFL Tests

A CFG production, a PDA transition and a language description often look like three separate questions. They are three views of the same computation. The usual loss happens when you know the definitions but cannot keep the input, state and stack aligned through one trace. One language settles all of it. L = {w c w^R} yields 011c110 in a four-step derivation, a three-state PDA accepts it in nine instantaneous descriptions, and its CFL family is closed under union but not under intersection.

Pushdown automata and CFG: two views of one language class

A context-free grammar is G = (V, Sigma, P, S): variables, terminals, productions and start symbol. A PDA is M = (Q, Sigma, Gamma, delta, q0, Z0, F): states, input and stack alphabets, transition relation, start state, bottom marker and final states.

A CFG generates strings. A PDA reads them with a LIFO stack. A language is context-free exactly when some nondeterministic PDA recognises it. Final-state and empty-stack acceptance describe the same CFL family after conversion, but trace the condition stated for the machine.

Below, the leftmost stack symbol is the top, epsilon consumes no input, and (state, unread input, stack) is an instantaneous description. For derivations, ambiguity and normal forms, see Context-Free Grammars and PDAs: CNF, GNF, Pumping Lemma.

CFG construction for 011c110

Fix L = {w c w^R | w belongs to {0,1}*}. The part after the single c reverses the part before it. Use

S -> 0S0 | 1S1 | c

Here V = {S} and the terminals are {0,1,c}. Each recursive production adds matching outer symbols; S -> c fixes the centre.

For w = 011, we have w^R = 110. The complete leftmost derivation is:

1. S => 0S0, using S -> 0S0.

2. 0S0 => 01S10, using S -> 1S1.

3. 01S10 => 011S110, using S -> 1S1.

4. 011S110 => 011c110, using S -> c.

The leaves read 0, 1, 1, c, 1, 1, 0. The grammar cannot generate 011c101 because 101 is not the reverse of 011; no production changes only one side of c.

PDA construction: push before c, pop after c

Use a final-state PDA with Q = {q_push, q_pop, q_accept}, input alphabet {0,1,c}, stack alphabet {0,1,Z0}, start q_push, bottom marker Z0, and final state q_accept.

For every stack symbol X, use delta(q_push,0,X) = (q_push,0X), delta(q_push,1,X) = (q_push,1X), and delta(q_push,c,X) = (q_pop,X). Then use delta(q_pop,0,0) = (q_pop,epsilon), delta(q_pop,1,1) = (q_pop,epsilon), and delta(q_pop,epsilon,Z0) = (q_accept,Z0).

Now trace the accepted string completely:

(q_push,011c110,Z0)

-> (q_push,11c110,0Z0)

-> (q_push,1c110,10Z0)

-> (q_push,c110,110Z0)

-> (q_pop,110,110Z0)

-> (q_pop,10,10Z0)

-> (q_pop,0,0Z0)

-> (q_pop,epsilon,Z0)

-> (q_accept,epsilon,Z0)

At c, stack 110Z0 matches the unread suffix. For 011c101, reading c and the first 1 leaves unread 01 and stack 10Z0. Input 0 does not match stack top 1, so no transition applies.

CFG-to-PDA conversion by stack simulation

The standard one-state construction accepts by empty stack. Start with S. Each production A -> alpha gives an epsilon transition replacing top A with alpha. A terminal transition consumes input a when top is a, then pops it. Production choice is nondeterministic.

Trace the stack simulation for input 011c110:

1. Start with stack S.

2. Apply S -> 0S0, resulting in stack 0S0.

3. Match input symbol 0, resulting in stack S0.

4. Apply S -> 1S1, resulting in stack 1S10.

5. Match input symbol 1, resulting in stack S10.

6. Apply S -> 1S1, resulting in stack 1S110.

7. Match input symbol 1, resulting in stack S110.

8. Apply S -> c, resulting in stack c110.

9. Match input symbol c, resulting in stack 110.

10. Match input symbol 1, resulting in stack 10.

11. Match input symbol 1, resulting in stack 0.

12. Match input symbol 0, resulting in stack epsilon, so the machine accepts by empty stack.

The invariant is that unread input matches the exposed terminal prefix, while the stack records the unfinished sentential form. In the reverse PDA-to-CFG construction, a triple variable [pXq] represents the strings the PDA can read while moving from state p to state q and net removing one stack symbol X. The grammar's start symbol seeds this correspondence with a production to [q0 Z0 q] for the relevant states, so the grammar and the machine describe the same language.

DPDA versus NPDA and the bounded-stack trap

For {w c w^R}, c announces the push-to-pop switch, so the machine can be deterministic. For {w w^R | w belongs to {0,1}*}, an NPDA can guess the midpoint, but no marker reveals it. This language is not deterministic context-free.

A bounded stack is still finite memory. With 3 states, stack alphabet {0,1,Z0}, and height capped at 10, the number of state-stack configurations is at most

3 x (1 + 3 + 3^2 + ... + 3^10) = 3 x 88,573 = 265,719.

The finite configuration set means this PDA recognises only a regular language. A large bound is not an unbounded stack.

CFL closure and decision properties

Let L1 = {a^i b^i c^j | i,j >= 0} and L2 = {a^i b^j c^j | i,j >= 0}. Each is context-free, but

L1 intersection L2 = {a^n b^n c^n | n >= 0},

which is not context-free. This proves non-closure under intersection. If CFLs were closed under complement, closure under union and De Morgan's law would force closure under intersection, contradicting this witness.

How GATE tests pushdown automata and CFG

The official GATE 2026 Computer Science syllabus lists context-free grammars and push-down automata, regular and context-free languages, the pumping lemma, Turing machines and undecidability.

GATE questions commonly use three concrete archetypes. First, trace the ID: given a PDA and a string, produce the instantaneous description after some moves, or decide acceptance, by recording state, unread input and stack at each step. Second, classify DCFL versus CFL: {w c w^R} is deterministic because c announces the switch, while {w w^R} is not. Third, prove a closure failure, usually by intersecting {a^i b^i c^j} with {a^i b^j c^j} to force {a^n b^n c^n}. Secure the regular-language boundary first with Finite Automata: DFA vs NFA and Subset Construction.

Continue with Context-Free Grammar MCQs: 11 Solved GATE Questions for a focused drill, then use GATE CS Exam Preparation for the wider Theory of Computation practice set.

Pushdown automata and CFG: the short version and next step

Five facts carry the topic: CFG productions generate a sentential form; a PDA stack stores unfinished obligations; c marks the push-to-pop switch; conversion exposes grammar symbols on the stack; closure and decidability need separate tables.

Self-check: w = 011 produces 011c110; at c, the stack is 110Z0; consuming 110 leaves Z0; and intersecting L1 with L2 forces {a^n b^n c^n}. Revisit any failed checkpoint before timing practice.

For Theory of Computation alongside the rest of GATE CS, GATE Guidance by Sanchit Sir is optional. For only this topic, the linked article and solved set are enough.