Constructing an NPDA for a Given CFG

To construct an NPDA from a context-free grammar (CFG), we use the standard correspondence: each CFG production is implemented as a nondeterministic stack rewrite step. Concretely, when the automaton sees a nonterminal $X$ on top of the stack, it can replace $X$ by the right-hand side of any production $X \to \gamma$ by pushing $\gamma$ onto the stack (in reverse order). Simultaneously, terminals are matched by consuming input symbols when the same terminal appears on top of the stack.

This course section applies that construction to the specific grammar:

$$\begin{aligned} S &\to \alpha ABB \mid \alpha AA \\ A &\to \alpha BB \mid \alpha \\ B &\to bBB \mid A \end{aligned}$$

where $\alpha$ denotes a (fixed) terminal string that must be read in the input. (If instead $\alpha$ is meant to be a single terminal, the construction specializes by using that one symbol as the read sequence.)

Key terms

• CFG
• Production
• Stack symbol
• Epsilon transition
• Start symbol

Grammar-to-NPDA construction pattern

The “recipe” for a CFG $G=(V,\Sigma,P,S)$ to an NPDA $M$ is:

1. Use stack to simulate the derivation.
2. Start with stack containing the start symbol $S$ (and typically a bottom marker).
3. For each production $X \to \gamma$ add an $\epsilon$-move that replaces $X$ by $\gamma$ on the stack.
4. For each terminal $a \in \Sigma$ add a move that consumes input $a$ when $a$ is on the stack top.
5. Accept by empty stack or by entering a final state after input is consumed (both are standard variants).

Why this works (intuitively)

A leftmost derivation in the CFG corresponds to a sequence of rewrites of the leftmost nonterminal. In the NPDA simulation, “rewriting” is done whenever a nonterminal is on top of the stack, and “reading” is done when a terminal is on top of the stack.

Note: “push reversed” means if $\gamma = Y_1Y_2\cdots Y_k$ then we push $Y_k,\ldots,Y_2,Y_1$ so that $Y_1$ becomes the new top (to be expanded/consumed next).

NPDA definition (formal transitions)

We must implement these productions:

• $S \to \alpha ABB \mid \alpha AA$
• $A \to \alpha BB \mid \alpha$
• $B \to bBB \mid A$

Assumptions about alphabets

Let $\u03a3$ contain at least $\u007b b \u007d \u222a$ symbols appearing inside $\alpha$. Terminals in $\alpha$ are treated as literal input symbols the NPDA will consume in order.

Define the stack alphabet:

$$\Gamma=\u007b Z_0, S, A, B \u222a \Sigma \u222a \text{(terminals inside }\alpha\text{)} \u007d$$

(Practically, $\Sigma$ already includes those terminals.)

States

Let $Q=\u007b q_0, q_{acc} \u007d$ (single working state + accept).

Start move

On initialization, push $S$ above the bottom marker:

• $\u0394(q_0,\u03b5,Z_0)=\u007b (q_0,SZ_0)\u007d$

(Interpretation: replace top $Z_0$ by $SZ_0$.)

$\epsilon$-transitions for the grammar’s nonterminals

We now add $\epsilon$ transitions that replace a stack-top nonterminal by the RHS string.

For $S$

1. For $S \to \alpha ABB$:

• If top is $S$, replace by the sequence $\alpha \, A \, B \, B$. So the NPDA push is: push RHS symbols in reverse order:
• push $B$, then $B$, then $A$, then the symbols of $\alpha$ in reverse, and keep them so that the leftmost symbol of $\alpha$ is consumed first.

2. For $S \to \alpha AA$ similarly: replace $S$ by $\alpha \, A \, A$.

For $A$

1. For $A \to \alpha BB$ replace $A$ by $\alpha \, B \, B$.
2. For $A \to \alpha$ replace $A$ by $\alpha$.

For $B$

1. For $B \to bBB$ replace $B$ by $b \, B \, B$.
2. For $B \to A$ replace $B$ by $A$.

To avoid ambiguity about the internal symbols of $\alpha$, we represent $\alpha$ as a concrete terminal string:

$$\alpha = a_1 a_2 \cdots a_k$$

Then a push for $\alpha$ means pushing $a_k,\ldots,a_2,a_1$ so that $a_1$ ends up on top.

Transitions written schematically

For clarity, we show the replacement rule in stack form.

$S$-productions

• If stack top is $S$, push $(\alpha ABB)$:

$$\Delta(q_0,\epsilon,S)\ni (q_0,\; \text{push}(\text{reverse}(\alpha)\; B\; B\; A))$$

• If stack top is $S$, push $(\alpha AA)$:

$$\Delta(q_0,\epsilon,S)\ni (q_0,\; \text{push}(\text{reverse}(\alpha)\; A\; A))$$

$A$-productions

• $A \to \alpha BB$:

$$\Delta(q_0,\epsilon,A)\ni (q_0,\; \text{push}(\text{reverse}(\alpha)\; B\; B))$$

• $A \to \alpha$:

$$\Delta(q_0,\epsilon,A)\ni (q_0,\; \text{push}(\text{reverse}(\alpha)))$$

$B$-productions

• $B \to bBB$:

$$\Delta(q_0,\epsilon,B)\ni (q_0,\; \text{push}(B\; B\; b))$$

because RHS is $bBB$; reversed push order puts $b$ first to be matched by input.

• $B \to A$:

$$\Delta(q_0,\epsilon,B)\ni (q_0,\; A)$$

Terminal matching transitions (consume input when terminal is on top)

For each terminal symbol $t$ (including $b$ and all $a_i$ from $\alpha$):

• If the stack top is $t$, consume $t$ and pop it:

$$\Delta(q_0,t,t)\ni (q_0,\epsilon)$$

Concretely, for the symbol $b$:

• $\Delta(q_0,b,b)=\{(q_0,\epsilon)\}$

And similarly for each $a_i$ in $\alpha$:

• $\Delta(q_0,a_i,a_i)=\{(q_0,\epsilon)\}$

Acceptance transition

Use acceptance by empty stack above bottom marker:

• If no input remains and top is $Z_0$, move to accept:

$$\Delta(q_0,\epsilon,Z_0)\ni (q_{acc},Z_0)$$

Alternatively, you can define $F=\u007b q_{acc}\u007d$.