Building NPDA from CFG

 

I. General rules (CFG → NPDA) — the standard construction

Build an NPDA
$M=(Q,\Sigma,\Gamma,\delta,q_0,Z_0,F)$ with a single “working” state $q_0$ plus an accept state $q_f$. Use acceptance by final state (or empty stack — equivalent variations exist).

1. Start: push the start symbol onto the stack.
   $\delta(q_0,\varepsilon,Z_0)\ni (q_0, S Z_0)$
   

2. Variable expansion (simulate productions):
   For every production $A \to X_1 X_2 \cdots X_n$ (each $X_i \in V\cup T$), add an ε-move that replaces $A$ on top of the stack with the string $X_1 X_2 \cdots X_n$(with $X_1$ becoming the new top).
   Formally: $\delta(q_0,\varepsilon, A)\ni (q_0, X_1 X_2\cdots X_n)$
   

   (This implements a leftmost derivation step by rewriting the stack top variable to its RHS.)

3. Match terminals with input:
   For each terminal $a$ add the transition that consumes $a$ from input only when $a$ is on the top of the stack:
   $\delta(q_0, a, a)\ni (q_0,\varepsilon)$
   (Pop the terminal from stack and consume the input symbol.)

4. Accept: when input is finished and the stack contains just the start marker $Z_0$, move to accept:
   $\delta(q_0,\varepsilon, Z_0)\ni (q_f, Z_0)$
   

Notes:

• The machine is nondeterministic because when the top is a variable that has several productions, the NPDA can nondeterministically choose any corresponding ε-move.

• The stack alphabet $\Gamma$ includes all grammar symbols (nonterminals and the terminals you push), plus $Z_0$.

---

Example:

S → a A

A → a A B C  |  b B  |  a

B → b

C → c

II. Apply the rules to the given grammar

1. Components

• Input alphabet $\Sigma = \{a,b,c\}$.

• Stack alphabet $\Gamma = \{S,A,B,C,a,b,c,Z_0\}$
  

• States $Q=\{q_0,q_f\}$, start $q_0$, final $q_f$.

2. Initialization

Push start symbol:

$$\delta(q_0,\varepsilon,Z_0)\ni (q_0,\;S Z_0).$$

3. Expansion rules (one ε-move per production)

For each grammar production add an ε transition that replaces the nonterminal on stack top by the RHS:

• For S → a A:

  $$\delta(q_0,\varepsilon, S)\ni (q_0,\; a\,A).$$
  

• For A → a A B C:

  $$\delta(q_0,\varepsilon, A)\ni (q_0,\; a\,A\,B\,C).$$
  

• For A → b B:

  $$\delta(q_0,\varepsilon, A)\ni (q_0,\; b\,B).$$
  

• For A → a:

  $$\delta(q_0,\varepsilon, A)\ni (q_0,\; a).$$
  

• For B → b:

  $$\delta(q_0,\varepsilon, B)\ni (q_0,\; b).$$
  

• For C → c:

  $$\delta(q_0,\varepsilon, C)\ni (q_0,\; c).$$
  

4. Terminal-matching transitions

For each terminal $t\in \{a,b,c\}:$

$$\delta(q_0,t,t)\ni (q_0,\varepsilon).$$

(These consume the input symbol $t$ only when that exact terminal is on top of the stack.)

5. Accept

When input is exhausted and only $Z_0$ remains:

$$\delta(q_0,\varepsilon,Z_0)\ni (q_f,Z_0).$$

---

III. Short description of how the NPDA works

• Start: stack = $Z_0$ Push $S$ (now top is $S$).

• While top is a nonterminal, nondeterministically choose one of its productions and replace the nonterminal by the RHS (push RHS symbols so the leftmost symbol becomes top).

• When the top is a terminal and matches next input symbol, consume that input and pop the terminal from stack.

• If input is fully consumed and stack reduced to $Z_0$, go to $q_f$ and accept.

This exactly simulates a leftmost derivation: expanding the leftmost nonterminal (stack top) into its RHS, then matching terminals as they appear.

---

IV. Worked example (derivation + NPDA trace)

Let’s generate the string aaabc (one possible string from the grammar). We’ll show the corresponding NPDA instantaneous descriptions (IDs). First a derivation in the grammar:

1. $S \Rightarrow aA$
   

2. choose $A \to a A B C$: $aA \Rightarrow a\;aABC$
   

3. choose $A \to a$: $a\;aABC \Rightarrow a\;a\;aBC$
   

4. $B \to b$: $a\;a\;aBC \Rightarrow a\;a\;a b C$
   

5. $C \to c$: $a\;a\;a b C \Rightarrow a\;a\;a b c$
   Final string: aaabc.

Now the NPDA simulation on input aaabc (stack shown with top at left):

Start: $(q_0,aaabc,Z_0)$

1. push S: $(q_0,\;aaabc,\;S Z_0)$ via $\delta(q_0,\varepsilon,Z_0)$.

2. expand S → aA: ε-move replacing S → aA
   $(q_0,aaabc,aA{Z}_0).$

3. top is terminal a and input starts with a: match (consume):
   $(q_0,aabc,A{Z}_0)\; via$$\delta(q_0,a,a)$.

4. expand A → a A B C (choose this production): ε-move
   $(q_0,\;aabc,\;a A B C Z_0)$.

5. match terminal a: $(q_0,abc,ABC{Z}_0)$

6. expand A → a (choose the third production of A): ε-move
   $(q_0,\;abc,\;a B C Z_0)$
   

7. match terminal a: $(q_0,\;bc,\;B C Z_0)$.

8. expand B → b: ε-move → stack becomes b C Z_0.

9. match terminal b: $(q_0,c,C{Z}_0).$

10. expand C → c: ε-move → stack c Z_0.

11. match terminal c: $(q_0,\;\varepsilon,\;Z_0)$.

12. input finished and top is $Z_0$: ε-move to accept: $(q_f,\epsilon ,Z_0).\; Accepted.$

---

V. Remarks & pedagogical points

• The NPDA construction is systematic: each grammar rule becomes an ε-transition that rewrites the nonterminal on the stack. Terminal symbols in RHS are treated as stack symbols and later matched to input by consuming transitions.

• Nondeterminism is how the NPDA chooses which production to apply when a nonterminal has several productions (e.g., A had three). The correct sequence of choices corresponds to a leftmost derivation of the string in the grammar.

• If you prefer, you can optimize the stack alphabet to avoid pushing terminals (instead push special stack symbols for terminals), but the above direct method is simplest to explain and prove correctness.

• The method works for arbitrary CFGs (after removing ε-productions/units if necessary, or adjusting acceptance), and is the standard proof that every CFL is accepted by some NPDA.

Example:

build the NPDA for the given grammar:

$$S \to aTb \;|\; b, \quad T \to aT \;|\; \epsilon$$

---

Step 1: Understand the language

• From $S \to b$, the string "b" is in the language.

• From $S \to aTb$:

  • $T \to \epsilon$ gives "ab".

  • $T \to aT \to aaT \to \dots \to a^n$ gives "a^n b".

✅ So the language is:

$$L = \{ b \} \cup \{ a^n b : n \geq 1 \}$$

That is, all strings of a’s followed by a single b, and also the special case "b".

---

Step 2: NPDA construction rules

We use the standard CFG → NPDA method:

• Two states: $q_0$ (start) and $q_1$ (processing).

• Push start symbol $S$ onto the stack.

• Expand variables nondeterministically.

• Match terminals against input.

• Accept by empty stack.

---

Step 3: NPDA definition

$$M = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, \emptyset)$$

• $Q = \{q_0, q_1\}$
  

• $\Sigma = \{a, b\}$
  

• $\mathrm{\Gamma }=\{a,b,S,T,Z_0\}$

• Start state: $q_0$

• Start stack symbol: $Z_0$

• Acceptance: empty stack

---

Step 4: Transitions

1. Initialization

   $$δ(q_0, ε, Z_0) = (q_1, SZ_0)$$
   

2. Expand productions of S

   • $S \to aTb$
     

     $$δ(q_1, ε, S) = (q_1, aTb)$$
     

   • $S \to b$
     

     $$δ(q_1, ε, S) = (q_1, b)$$
     

3. Expand productions of T

   • $T \to aT$
     

     $$δ(q_1, ε, T) = (q_1, aT)$$
     

   • $T \to ε$
     

     $$δ(q_1, ε, T) = (q_1, ε)$$
     

4. Terminal matching

   • Match input a:

     $$δ(q_1, a, a) = (q_1, ε)$$

   • Match input b:

     $$δ(q_1, b, b) = (q_1, ε)$$
     

---

✅ This NPDA accepts strings "b", "ab", "aab", "aaab", …" by empty stack.