Equivalence of CFGs and PDAs: Question bank — Coding deep dive

Before you start, refresh the vocabulary, the two acceptance modes, and the two constructions we lean on everywhere below. Nothing on this page uses a symbol we have not first pinned down here.

Definition Words and symbols you must own

A sentential form is any string of terminals and variables you can reach part-way through a derivation (e.g. $a S b$ ).
A leftmost derivation is one that always expands the leftmost variable first; this matters because a stack always exposes only its top, so left-to-right expansion is exactly what a stack can carry out.
Net-zero (balanced) stack usage means the stack ends at the exact height it started, and never dips below that starting height in between — like pushing and later popping matching brackets. Bracket nesting here means: an inner pushed symbol is popped before the outer symbol that surrounds it, exactly like matched parentheses ( ( ) ).
Nondeterminism means the machine may have several legal moves and we accept if at least one choice-path succeeds.
The symbol $\cdot$ (a centred dot) means string concatenation — writing one string immediately after another, so $ab \cdot c d = ab c d$ .

See Pushdown Automata, Context-Free Grammars, and Leftmost Derivations and Parse Trees for fuller treatments; everything needed below is recapped right here.

Formula Construction B — PDA

$\Rightarrow$ CFG (the balanced-triple grammar) First normalise the PDA so it accepts by empty stack and every move either pushes exactly one stack symbol or pops exactly one (never a pure replacement, never zero-change). Then, for each pair of states $p, q$ , introduce a variable $A_{pq}$ with the intended meaning: $A_{pq} \Rightarrow^{*} w ⟺ the PDA can go from state p to state q reading w with net-zero stack usage .$ The rules that realise this meaning (here $p, q, r, s$ all range over states — $p$ = start of the run, $q$ = end of the run, and $r, s$ are intermediate states that appear where a run is cut):

Base case: $A_{pp} \to ε$ (staying put, reading nothing, no net stack change).
Split rule: $A_{pq} \to A_{p r} A_{r q}$ for every intermediate state $r$ (the stack returns to start height at some mid-run state $r$ , splitting the run in two).
Match rule: here $r$ is the state the machine is in just after the first push, and $s$ is the state it is in just before the final pop. If the PDA, on reading $a$ from $p$ , pushes a stack symbol $t$ and moves to $r$ , and later, on reading $b$ from $s$ , pops that same $t$ and moves to $q$ , add $A_{pq} \to a A_{r s} b .$ Here $t$ is the "bottom bracket": pushed first, popped last, with $A_{r s}$ handling everything in between above it.

With these boxes in hand, every trap below is self-contained.

True or false — justify

A CFG and a PDA can describe exactly the same class of languages.

True. This is the theorem itself:

L

is context-free

⟺

some PDA accepts

L

; the shared engine is a single stack that mirrors grammar recursion.

The equivalence holds even for deterministic PDAs, since determinism is just a special case.

False. The CFG↔PDA equivalence needs nondeterministic PDAs; deterministic PDAs (Deterministic PDAs and DCFLs) recognize only a proper subset (the DCFLs), e.g. they cannot accept

{w w^{R}}

Acceptance by final state and acceptance by empty stack recognize different language classes.

False. They recognize the same class: from an empty-stack PDA you build a final-state one by pushing a private bottom marker

Z_{0}

and entering an accept state only when it resurfaces, and vice-versa. So we freely pick whichever mode is convenient.

A PDA with two stacks is still limited to context-free languages.

False. Two stacks let the machine simulate a Turing machine (one stack = tape left of the head, one = right), so it escapes the context-free class entirely. Exactly one stack is what makes the equivalence hold.

In the CFG→PDA construction, the PDA needs many control states to track which rule it is applying.

False. A single state suffices (see Construction A), because a grammar has no "control state" — all live information sits in the sentential form, which the PDA stores entirely on its stack.

The invariant "(input read)

\cdot

(stack) = current sentential form" (where

\cdot

is concatenation) holds only at acceptance.

False. It holds at every step of the simulation; that is precisely why it proves correctness — acceptance is just the special moment when the stack is empty and all input is read.

A_{pq}

(from Construction B) stands for "there exists some path from state

p

to state

q

False. It means a path that reads some

w

and nets to zero stack change (balanced, never dipping below start height). Plain reachability ignores the stack and would over-generate.

Since

S \to a S b ∣ ε

came back out of the PDA→CFG trick, the two constructions are literally inverse functions.

False. They are inverse in spirit, not as functions — running CFG→PDA→CFG need not return a syntactically identical grammar, only an equivalent one generating the same language.

The rule

A_{pp} \to ε

is optional decoration.

False. It is the base case: staying at the same state reading nothing with no net stack change is a genuine balanced run, and without it recursion never terminates and no string is generated.

Every context-free language is accepted by some PDA whose input is always consumed one symbol per move.

False. The CFG→PDA machine uses

ε

-moves (consuming no input) whenever it expands a variable; only terminal-matching moves consume input.

A worked trace to anchor the ideas

Worked example

$G : S \to a S b ∣ ε$ run on $aabb$ via Construction A (stack top written on the left) Read each line as Step — Move (why) — Unread input — Stack:

Step 0 — start — unread $aabb$ — stack $S$ .
Step 1 — expand $S \to a S b$ ( $ε$ -move, reads nothing) — unread $aabb$ — stack $a S b$ .
Step 2 — match $a$ (stack-top $a$ = next input $a$ ) — unread $abb$ — stack $S b$ .
Step 3 — expand $S \to a S b$ — unread $abb$ — stack $a S bb$ .
Step 4 — match $a$ — unread $bb$ — stack $S bb$ .
Step 5 — expand $S \to ε$ (pop $S$ , push nothing) — unread $bb$ — stack $bb$ .
Step 6 — match $b$ — unread $b$ — stack $b$ .
Step 7 — match $b$ — unread $ε$ — stack empty → accept.

Notice every expand line leaves the unread-input unchanged (that is the $ε$ ), and only match lines shrink it. At every line, (input read) $\cdot$ (stack) — concatenating the already-read prefix with the remaining stack — reads out $aabb$ 's current sentential form.

Worked example The same language through Construction B, and why it returns an equivalent grammar

Take the two-state PDA: in $p$ , reading $a$ pushes $t$ and stays in $p$ ; reading $b$ pops $t$ and moves to $q$ ; in $q$ , reading $b$ pops $t$ and stays in $q$ . Acceptance by empty stack, with the start being the run $A_{pq}$ (from start state $p$ to the state $q$ where the stack empties).

Apply the match rule to the outer bracket: reading $a$ from $p$ pushes $t$ moving to $p$ (so here $r = p$ ), and reading $b$ from $q$ pops that $t$ moving to $q$ (so here $s = q$ ). This yields $A_{pq} \to a A_{pq} b$ — a genuinely recursive rule on the single variable $A_{pq}$ .
The innermost bracket bottoms out when the first-pushed $t$ is matched directly: reading $a$ from $p$ pushes $t$ to $p$ , then reading $b$ from $p$ pops it moving to $q$ — giving $A_{pq} \to a A_{pq} b$ again, whose inner $A_{pq}$ can finish via the base case $A_{q q} \to ε$ (or $A_{pp} \to ε$ when no letters remain).
So the only generating variable is $A_{pq}$ , obeying $A_{pq} \to a A_{pq} b ∣ ε$ . Renaming that single variable $A_{pq}$ to $S$ gives $S \to a S b ∣ ε$ . We rename $A_{pq}$ (not $A_{pp}$ ) because $A_{pq}$ is the start variable that generates the language; the base-case variables $A_{pp}, A_{q q}$ only supply the empty terminating branch. The recovered grammar is equivalent to, not necessarily identical to, the original — the constructions are inverse in spirit.

Spot the error

"In CFG→PDA, when we expand a variable

A

using rule

A \to a B c

, the PDA also reads an input symbol during that expansion."

Error: expansion is an

ε

-move — it consumes no input. Input is consumed only later, when the terminal

a

sits on top of the stack and is matched against the next input symbol.

"To match a terminal

a

on the stack, the PDA pushes

a

and moves on."

Error: matching pops

a

and pushes nothing (

δ (q, a, a) ∋ (q, ε)

). The terminal was a promise already on the stack; matching fulfills it by removing it, not by adding more.

"Rule

A_{pq} \to A_{p r} A_{r q}

works for one specific well-chosen

r

Error: the grammar adds this split rule for all intermediate states

r

, and the derivation picks the right one. The split can happen at any mid-run moment the stack returns to its start height.

"In the match rule

A_{pq} \to a A_{r s} b

, the pushed symbol and the popped symbol may differ."

Error: recall from Construction B that the pushed stack symbol

t

(pushed when leaving

p

a

toward

r

) must be the same

t

popped when entering

q

b

from

s

— it is the bottom bracket. Mismatched symbols do not correspond to any valid balanced run.

"We only need the split rule OR the match rule, since one subsumes the other."

Error: both are required and they are exhaustive together — the first pushed symbol is popped either at the very end (match rule) or strictly earlier (split rule). Drop either and you miss half of all balanced runs.

"Determinizing the CFG→PDA construction just removes redundant guesses without losing languages."

Error: the guessing (which rule to expand) is essential. Forcing determinism restricts you to DCFLs, a strict subset — e.g.

{w w^{R}}

over

{a, b}

needs nondeterminism.

"To run PDA→CFG we can skip normalizing the PDA and read off triple-rules directly."

Error: the triple trick requires the normal form where every move pushes exactly one symbol or pops exactly one (no pure replacements, no zero-change moves) and acceptance is by empty stack. Without it, the "one push, one matching pop" bracket structure isn't guaranteed.

Why questions

Why does a stack (rather than a counter or a queue) capture context-free languages?

Because grammar derivations are nested — a variable expands inside another expansion — and nesting is exactly last-in-first-out bracket structure, which is what a stack stores. A queue (FIFO) would break the nesting order.

Why store the "unmatched suffix of the sentential form" on the stack instead of the whole string?

Because the prefix already matched against input is done and gone; only the part we still "owe" (terminals still to match, variables still to expand) needs recording, and that suffix behaves exactly like a stack under leftmost derivation.

Why does the PDA→CFG variable definition insist the stack never dips below its starting height?

If it dipped below, the run would be popping symbols that belong to an outer bracket — that outer structure would be handled by a different (enclosing) variable. Staying at-or-above keeps each variable responsible for one balanced layer.

Why is the CFG→PDA machine single-state but the PDA→CFG grammar has many variables

A_{pq}

The grammar side must encode the PDA's states, and it does so inside variable subscripts (

p, q

) rather than in a control unit. The single-state PDA had nothing to encode, so the asymmetry is just where the state information lives.

Why does simulating a leftmost derivation (not any derivation) make the stack simulation clean?

Leftmost derivation always expands the leftmost variable, matching the fact that a stack always exposes its top. Any-order derivation would need access to variables buried in the middle, which a stack forbids. See Leftmost Derivations and Parse Trees.

Why can we use empty-stack acceptance for the PDA→CFG direction without loss of generality?

Because empty-stack and final-state acceptance are equivalent for PDAs, and empty-stack directly encodes "the whole balanced run finished," which is exactly the

A_{pq}

semantics the grammar needs.

Edge cases

What does the CFG→PDA machine do with the empty string when

ε \in L

(e.g. rule

S \to ε

It applies the

ε

-expansion

δ (q, ε, S) ∋ (q, ε)

, popping

S

with no input read, leaving the stack empty and accepting — so

ε

is handled by an expansion move, not a match move.

If the grammar has a rule

A \to ε

, does the PDA read any input for it?

No. It pops

A

and pushes the empty string, consuming no input — an

ε

-move like every expansion, correct because applying a rule never consumes input.

What happens in CFG→PDA if the top of the stack is a terminal

a

but the next input symbol is

b \neq = a

That particular nondeterministic path dies (no matching move). Acceptance requires some path to succeed, so a wrong guess simply prunes itself and other paths continue.

What is

A_{pq}

when

w = ε

and

p = q

It is the base case

A_{pp} \to ε

: going nowhere reads the empty string with zero net stack change — the smallest balanced run.

Does the equivalence still hold for a finite language (no recursion at all)?

Yes. A finite language is trivially context-free, and its PDA simply never needs to reuse the stack recursively — the theorem covers this as a degenerate case where the recursion depth is bounded.

If the PDA never touches its stack (acts like a finite automaton), is the resulting language still context-free?

Yes — every regular language is context-free (regular

⊊

context-free). The stack is available but unused, giving a balanced-but-trivial run for every accepted string.

Can a single string have two accepting runs in the CFG→PDA machine?

Yes, if the grammar is ambiguous the string has multiple leftmost derivations, each giving a distinct accepting path. Nondeterminism accepts as long as at least one succeeds, so ambiguity is harmless for recognition. See Leftmost Derivations and Parse Trees.

What if the PDA can empty its stack in the middle of reading input and then push again — does one

A_{pq}

cover that?

No single match-rule variable covers it; that mid-run return to start height triggers the split rule

A_{pq} \to A_{p r} A_{r q}

, factoring the run into two consecutive balanced pieces.

Why must PDA→CFG normalisation eliminate "pure replacement" (zero net stack change) moves before we start?

Because such a move changes neither height nor bracket structure, so it fits neither the push nor the pop half of the match rule; we rewrite each into a push-then-pop pair so every move is cleanly a single push or single pop and the triple grammar can capture it.

ε

-loops in the PDA (an infinite cycle of

ε

-moves that never touches input or net stack height) break the PDA→CFG construction?

No — they only add derivations for

ε

(or re-derive the same

w

), never a new string, so

L (M)

is unchanged. The grammar stays finite because it enumerates state-pairs

A_{pq}

, not individual runs, so a cycle contributes at most a

A_{pp} \to ε

-style self-reference rather than infinitely many rules.

Recall One-line self-test

What does $δ (p, x, T) ∋ (r, γ)$ mean? ::: In state $p$ , optionally reading $x$ and popping stack-top $T$ , the PDA may go to $r$ and push $γ$ .
What makes two stacks too powerful? ::: They simulate a Turing machine, leaving the context-free class.
Where does the PDA→CFG grammar store PDA states? ::: In the subscripts $p, q$ of each variable $A_{pq}$ .
When is input consumed in CFG→PDA? ::: Only during a terminal match, never during expansion.
The two exhaustive PDA→CFG cases? ::: First pushed symbol popped at the very end (match) or earlier (split).
Why normalise the PDA first? ::: So every move is a single push or single pop, matching the triple grammar's bracket structure.