CFG ⟹ Nondeterministic PDA (Empty Stack Acceptance)

Let $G=(V,\Sigma,R,S)$ be a context-free grammar (CFG). Its language $L(G)$ is generated by all terminal strings obtainable from $S$ via derivations using productions in $R$. We prove that there exists a nondeterministic pushdown automaton (PDA) that accepts exactly $L(G)$ by empty stack.

We will construct a nondeterministic PDA $P$ that simulates leftmost derivations in a “stack-as-sentential-form” manner: the PDA nondeterministically replaces a nonterminal on the stack using one grammar production, and consumes terminals by matching them against the input. This yields acceptance by empty stack whenever the grammar derivation produces the entire input and empties the sentential form.

Key concepts: context-free grammar , sentential form , leftmost derivation , nondeterministic PDA , empty-stack acceptance.

The construction

Define the PDA $P=(Q,\Sigma,\Gamma,\delta,q_0,Z_0)$ (no final states are needed for empty-stack acceptance). Use:

• $Q=\{q\}$ (single control state),
• $\Gamma = V \cup \Sigma \cup \{Z_0\}$,
• initial stack symbol $Z_0$,
• start configuration corresponds to pushing the start symbol $S$ above $Z_0$.

The PDA uses nondeterminism to choose a production whenever the top-of-stack is a nonterminal. When the top-of-stack is a terminal that matches the current input symbol, the PDA pops it while consuming the symbol. Formally, the transition relation $\delta$ will include two kinds of moves.

We will use the following construction idea: “production simulation” and “terminal matching”.

Formal transition rules

Let the PDA have a single state $q$. We write transitions as [ \delta(q,; \text{inputSymbol or } \epsilon,; \text{stackTop}) ;\ni; (q,; \text{stackReplacement}) ] where “stackReplacement” is a string that will replace the popped stackTop symbol.

1. Initialization (push $S$): [ \delta(q,\epsilon,Z_0)\ni (q,SZ_0) ]

2. Production step (replace a nonterminal $A$):
   For every production $A\\to\\alpha$ in $R$ where $A\\in V$ and $\\alpha\\in (V\\cup\\Sigma)^*$, add: [ \delta(q,\epsilon,A)\ni \left(q,\text{rev}(\alpha)\right) ] where $\\text{rev}(\\alpha)$ denotes the reverse string of $\\alpha$ so that the leftmost symbol of $\\alpha$ becomes the next stack-top to be handled.

3. Terminal step (match and consume):
   For each $a\\in\\Sigma$: [ \delta(q,a,a)\ni (q,\epsilon) ]

No other moves are required.

[CalloutBlock tip] type: "tip" title: "Why the reverse string?" content: "When you pop the stack, you effectively process symbols from left to right in the intended sentential form. Since stacks are LIFO, you push the right-hand side $\\alpha$ in reverse so that the leftmost symbol of $\\alpha$ is on top and processed first."

Correctness Proof

We show $L(P)=L(G)$ under empty-stack acceptance by proving both containments:

1. If $w\\in L(G)$ then $P$ accepts $w$ by empty stack.
2. If $P$ accepts $w$ by empty stack then $w\\in L(G)$.

The heart of the proof is an invariant: at any point, the stack (ignoring $Z_0$) is a sentential form reachable from $S$, and the PDA’s remaining input corresponds to what still must be matched/produced.

Invariant (sentential form alignment)

Define the stack content (above $Z_0$) as a string $\\gamma \\in (V\\cup\\Sigma)^*$, representing the “yet-to-be-produced” sentential form. The PDA configuration after some steps has the form: [ (q, ; x, ; \gamma Z_0) ] where $x$ is the remaining unread input string.

Invariant statement: If $\\gamma$ is the current sentential form in the grammar derivation such that $\\gamma \\Rightarrow^* x$ (producing exactly the remaining terminals in $x$), then the PDA can reach and maintain the configuration above through matching and production steps.

This invariant is proven via correspondence between:

• grammar production application $A\\to\\alpha$ and PDA nondeterministic replacement of top $A$ by $\\alpha$,
• terminal emission of the leftmost terminal symbol and PDA terminal matching move.

(1) If $w\\in L(G)$, then $P$ accepts $w$ by empty stack

Assume $w\\in L(G)$. Then there exists a derivation: [ S \Rightarrow^* w ] Consider a leftmost derivation (every derivation can be refined into a leftmost one). A leftmost derivation expands the leftmost nonterminal at each step, producing terminals in the correct left-to-right order.

We simulate this derivation with the PDA:

• Initially, $P$ pushes $S$, so the stack equals the current sentential form.
• Whenever the grammar applies a production $A\\to\\alpha$ to the leftmost nonterminal $A$ in the sentential form, the PDA has $A$ at the top of stack and can nondeterministically apply the production step to replace $A$ by $\\alpha$.
• Whenever the sentential form has a leftmost terminal $a$ to be produced next, that terminal appears on top of the PDA stack, and the PDA can apply the terminal matching transition $\delta(q,a,a)$ to consume $a$ from input and pop it.

At the end of the derivation, the sentential form becomes the terminal string $w$ and then is consumed symbol-by-symbol. After the entire input $w$ is read, the stack symbols above $Z_0$ have all been popped, so the PDA can reach an empty stack configuration (by having popped everything that was representing $w$). Hence it accepts by empty stack.

(2) If $P$ accepts $w$ by empty stack, then $w\\in L(G)$

Assume the PDA $P$ accepts $w$ by empty stack. Then there exists a computation that, starting from the initial configuration, consumes all input symbols and results in an empty stack.

Track the PDA’s stack evolution (excluding $Z_0$):

• Each time the PDA replaces a nonterminal $A$ on top of the stack via the rule $\delta(q,\epsilon,A)\ni(q,\\text{rev}(\\alpha))$, we interpret it as a grammar production step $A\\to\\alpha$.
• Each time the PDA matches a terminal $a$ via $\delta(q,a,a)$, we interpret it as the grammar having that terminal as part of its leftmost sentential form at that stage.

Because the PDA pops all symbols above $Z_0$ exactly when it consumes terminals from the input, the sequence of production choices corresponds to a valid derivation from $S$ that yields $w$.

Therefore, $S\\Rightarrow^* w$, so $w\\in L(G)$.

Summary (Language equality)

From the two containments proved above, we conclude: [ L(P)=L(G) ] where acceptance is defined as reaching empty stack after consuming the entire input.

This is the core direction of the CFG–PDA equivalence theorem: CFGs and nondeterministic PDAs describe the same class of languages (the context-free languages), with different but equivalent acceptance conventions (final states vs empty stack).