Constructing a PDA for a Given Grammar and Testing Acceptance of a String

We construct a PDA (pushdown automaton) from a context-free grammar (CFG) using the standard “simulate leftmost derivations with a stack” method. For CFG production rules, the PDA replaces a nonterminal on top of the stack with the RHS of a production, while terminal symbols on top must match the current input symbol.

Grammar

• $S \to 0BB$
• $B \to 0S \mid 1S \mid 0$

We will build a PDA that accepts exactly the language generated by this CFG (with acceptance by empty stack).

Mermaid view of the derivation simulation:

transition function
nonterminal expansion
leftmost derivation simulation
acceptance by empty stack
stack top

Standard CFG $\to$ PDA construction (high level)

Let the PDA have:

• one start state $q_{\text{start}}$,
• a set of states where the PDA “processes input”,
• a stack alphabet containing terminals and nonterminals,
• acceptance by empty stack.

The core mechanics are:

1. Push start symbol $S$ onto the stack.
2. While input remains:
   • If stack top is a nonterminal $X$, nondeterministically choose a production $X \to \alpha$ and replace $X$ with $\alpha$ (push $\alpha$ onto the stack in reverse order).
   • If stack top is a terminal $a$, and next input symbol is $a$, pop it and consume the input symbol.

This is the generic method for constructing a PDA equivalent to a CFG.

production rule
nondeterminism
stack replacement
consumption step

The PDA definition (explicit transitions)

We describe the PDA $M=(Q,\\Sigma,\\Gamma,\\delta,q_{start})$ with acceptance by empty stack.

• $Q=\{q_{start},q\}$
• \\Sigma=\{0,1\\}
• \\Gamma=\{0,1,S,B\\} (stack holds terminals and nonterminals)
• Start state: $q_{start}$
• Stack acceptance: empty stack

1) Initialization

We assume the stack is empty initially. Use an epsilon transition to push $S$:

• $\delta(q_{start},\\varepsilon,\\varepsilon)\\ni(q,S)$

(If you prefer a bottom marker, the same idea applies; the construction is equivalent.)

2) Terminal matching

For any time the top of stack is a terminal, it must match the input symbol:

• $\delta(q,0,0)\\ni(q,\\varepsilon)$ (match/read 0, pop 0)
• $\delta(q,1,1)\\ni(q,\\varepsilon)$ (match/read 1, pop 1)

3) Nonterminal expansions

Now encode the grammar productions by stack replacement.

Production $S \\to 0BB$
Pop $S$, push RHS symbols $0,B,B$ (in reverse push order so that the first symbol $0$ ends up on top):

• $\delta(q,\\varepsilon,S)\\ni(q,0BB)$ (read as “replace $S$ by stack string $0BB$ with $0$ on top”)

Production $B \\to 0S$

• $\delta(q,\\varepsilon,B)\\ni(q,0S)$

Production $B \\to 1S$

• $\delta(q,\\varepsilon,B)\\ni(q,1S)$

Production $B \\to 0$

• $\delta(q,\\varepsilon,B)\\ni(q,0)$

That fully specifies the PDA behavior.

stack string
epsilon transition
match transition
replacement

PDA sanity check on structure

From $S\\to 0BB$, any accepted string must begin with $0$, because the PDA must eventually expand $S$ and the resulting stack prefix forces the first terminal to be $0$.

Then each $B$ expands using:

• $B\\to 0$ (contributes a single $0$), or
• $B\\to 0S$ (contributes a $0$ then whatever $S$ generates), or
• $B\\to 1S$ (contributes a $1$ then whatever $S$ generates).

This recursive structure guarantees that strings have form:

• $0$ followed by two “$B$-generated” segments.

Test whether $0104$ is accepted

First, note the mismatch: the grammar terminals are only $0$ and $1$, so $4$ is not in the input alphabet $\Sigma=\{0,1\}$.

So the string “$0104$” cannot be accepted because the PDA has no transition that can read a symbol $4$.

Formally, during matching transitions, the PDA can only consume an input symbol when it matches a terminal on the top of stack, and terminals available are only $0$ and $1$. Therefore, when the PDA reaches the input symbol $4$, there is no valid move to consume it, and the run blocks.

terminal alphabet
undefined input symbol