PDA Design and Basics: Worked Stack Traces and Exam Question Patterns

A PDA diagram looks like a finite automaton until you must decide exactly what its stack contains after each move. That is where guessed transitions and reversed stack notation cause trouble. This guide fixes one convention, designs a complete machine, and traces accepted and rejected strings step by step. You can place the topic in the wider CS fundamentals sequence as you work.

What a Pushdown Automaton Adds to a Finite Automaton

A pushdown automaton, or PDA, combines finite control with an unbounded last-in, first-out stack. The stack remembers an unmatched quantity, such as how many a symbols still need corresponding b symbols. It is not random extra storage.

A DFA or NFA chooses its next move from the current state and input symbol, as Finite Automata: DFA vs NFA and Subset Construction explains. A PDA can also inspect and replace the stack top.

Formally, M = (Q, Sigma, Gamma, delta, q0, Z0, F). These are the states, input alphabet, stack alphabet, transition relation, start state, bottom marker, and accepting states. Our machine uses Sigma = {a,b}, Gamma = {A,Z0}, start state q0, and final state qf. NPDAs recognise exactly the context-free languages. DPDAs recognise only the deterministic context-free subset.

Read Every PDA Transition Without Guessing

Throughout this article, the leftmost stack symbol is the top. Read delta(q,x,X) contains (p,gamma) in a fixed order: enter the move in state q, consume x, pop top symbol X, push replacement string gamma, and enter state p. If x = epsilon, consume no input. If gamma = epsilon, push nothing.

Three moves from the main machine show the pattern:

• delta(q0,a,Z0) = (q0,AZ0) reads the first a and places A above Z0.

• delta(q0,a,A) = (q0,AA) reads another a and adds another A.

• delta(q0,b,A) = (q1,epsilon) reads the first b, pops one A, and enters the popping phase.

An instantaneous description has the form (state, unread input, stack). Some textbooks write the stack top on the right. Follow the convention stated in the question and never mix the two forms inside one trace.

Design a PDA for L = {a^n b^n | n >= 1}

Start with the invariant. While reading a, push exactly one A per symbol. On the first b, move permanently to the pop phase and remove one A per b. Accept only after all input is consumed and the stack has returned to Z0. Separate phases enforce both the order and equal counts.

The complete final-state PDA is:

• Q = {q0,q1,qf}, Sigma = {a,b}, and Gamma = {A,Z0}

• start state q0, initial stack symbol Z0, and F = {qf}

• delta(q0,a,Z0) = (q0,AZ0)

• delta(q0,a,A) = (q0,AA)

• delta(q0,b,A) = (q1,epsilon)

• delta(q1,b,A) = (q1,epsilon)

• delta(q1,epsilon,Z0) = (qf,Z0)

There are no other transitions. In particular, there is no epsilon move from (q0,Z0) to qf. The empty string therefore rejects, so this machine implements n >= 1, not n >= 0.

Trace aabb From Start to Acceptance

Apply one transition at a time:

1. (q0,aabb,Z0) |- (q0,abb,AZ0): read a and push A.

2. (q0,abb,AZ0) |- (q0,bb,AAZ0): read a and push another A.

3. (q0,bb,AAZ0) |- (q1,b,AZ0): read b, pop A, and enter q1.

4. (q1,b,AZ0) |- (q1,epsilon,Z0): read b and pop the second A.

5. (q1,epsilon,Z0) |- (qf,epsilon,Z0): consume no input and enter qf.

The two a symbols create two A symbols, and the two b symbols remove them. The bottom marker remains. Acceptance occurs because the unread input is epsilon and the machine is in qf.

Now trace aab. It reaches (q1,epsilon,AZ0). The input is empty, but one unmatched A remains and no move to qf applies, so the string rejects.

Final-State Acceptance, Empty-Stack Acceptance, and Determinism

The machine above accepts by final state and leaves Z0 on the stack. An empty-stack variant can replace its last move with delta(q1,epsilon,Z0) = (q1,epsilon). It accepts after consuming the full input and removing the bottom marker.

For NPDAs, final-state and empty-stack acceptance have equal language power after a proper construction. The same transition set does not automatically satisfy both definitions, however. An empty stack is not acceptance while unread input remains.

The listed machine is deterministic. For each reachable combination of state, next input, and stack top, at most one move applies, and an epsilon move never competes with an input-consuming move for the same state and stack top. Nondeterminism becomes useful when a PDA must guess a boundary or choose a grammar production.

Convert a CFG Production Into PDA Stack Operations

Consider the grammar S -> aSb | epsilon, which generates {a^n b^n | n >= 0}. A standard one-state NPDA begins with S on the stack. Its relation includes both (q,aSb) and (q,epsilon) in delta(q,epsilon,S), plus the matching moves delta(q,a,a) = (q,epsilon) and delta(q,b,b) = (q,epsilon). It accepts by empty stack after consuming all input.

For aabb, the full trace is:

(q,aabb,S) |- (q,aabb,aSb) |- (q,abb,Sb) |- (q,abb,aSbb) |- (q,bb,Sbb) |- (q,bb,bb) |- (q,b,b) |- (q,epsilon,epsilon)

The moves are, in order: expand S, match a, expand S, match a, choose S -> epsilon, match b, and match b. Grammar variables are expanded on the stack, terminals are matched with input, and nondeterminism chooses a production. Context-Free Grammars and Pushdown Automata: CFGs, PDAs, and a Worked Example also places this construction beside CNF, GNF, and the pumping lemma.

Three PDA Design Traps and Their Exact Failures

1. Accepting on input exhaustion alone. Input aab ends with stack AZ0, so one a remains unmatched. Require complete input consumption and the stated final-state or empty-stack condition.

2. Forgetting phase order. Input abab enters q1 after its first b. There is no input-consuming move for the next a, so no accepting computation exists. Keep separate push and pop phases, with no a transition out of q1.

3. Ignoring underflow or replacement order. Input abb reaches (q1,b,Z0). There is no input-consuming move for the extra b; taking the epsilon move leaves that b unread and still rejects. Do not add a b,Z0 pop transition for this language, and always state which side holds the stack top.

PDA Exam Questions and the Short Revision Path

Common question shapes ask you to identify a graph's language, complete a transition, trace a string, compare acceptance modes, convert between a CFG and PDA, or test determinism. Treat these as forms to practise, not as claims about official frequency or weightage.

Use three rapid checks. For aaabbb, maximum stack height is 4 when Z0 is counted because the stack becomes AAAZ0; it is 3 when only pushed A symbols count. Input aabbb rejects because one b remains when the stack reaches Z0. Reaching qf with unread input also cannot accept under the full-input requirement.

The short design method is: identify what must be remembered, choose the stack symbol, separate input phases, then test one valid and two invalid strings. For the direct next lesson, use Theory Of Computation / Automata Theory. If you need that subject inside a wider study sequence, follow GATE Guidance by Sanchit Sir.