I. Conversion of CFG to PDA

1. Construction

Let $G=(V,T,Q,S)$ be a CFG. Construct the PDA $P$ that accepts $L(G)$ by empty stack as follows:

$$ P=(\{q\}, T, V\cup T, \delta, q, S) $$

where transition function $\delta$ is defined by:

1. Type 1 rules: (Rule 2 on book)

   $$

   \text{For each terminal $a$, $δ(q, a, a) = \{(q, ε)\}.$}

   $$

   This step does not change the LSF (Left-Sentential Form) represented, but “moves” responsibility for $a$ from the stack to the consumed input.

2. Type 2 rules: (Rule 1 on book)

   $$ \delta(q, \varepsilon, A) = \{(q,\beta)~|~A\rightarrow\beta\text{ is a production of }G\} $$

   Guess a production for A, and represent the next LSF in the derivation.

Intuition

At each step, P represents some left-sentential form (step of a leftmost derivation).

• If the stack of P is $\rm a$, and P has so far consumed $\rm x$ from its input, then P represents left-sentential form $\rm xa$.
• At empty stack, the input consumed is a string in L(G).

2. Proof

To show that $(q, wx, S)\vdash^* (q, x, \alpha)$ for any x if and only if $S \Rightarrow^*_{lm}w\alpha$

Part 1 - Only if

Proved by an induction on the number of steps made by P

Basis: 0 steps ⇒ $\alpha = S$, $w = ε$, and $S \Rightarrow^*_{lm} S$ is surely true

Induction: Consider n moves of P. Assume the IH for sequences of n-1 moves.

There are two cases, depending on whether the last move uses a Type 1 or Type 2 rule.

1. Type 1 Rule: $(q, yax, S) \vdash^* (q, ax, a\alpha) \vdash (q, x, \alpha)$, where $ya=w$
   • Then $S \Rightarrow^_{lm} ya\alpha$, and since $ya=w$, $S \Rightarrow^_{lm}w\alpha$
2. Type 2 Rule: $(q, wx, S) \vdash^* (q, x, A\beta) \vdash (q, x, \gamma\beta)$, where $A\rightarrow\gamma$ is a production and $\alpha=\gamma\beta$
   • $S \Rightarrow^*_{lm}wA\beta \Rightarrow w\gamma\beta = w\alpha$

Part 2 - If

Suppose $w$ is in $L(G)$. Then $w$ has a lm derivation:

$$ \gdef\rlm{\Rightarrow_{lm}}

S=\gamma_1 ~\rlm \gamma_2~\rlm … ~\rlm \gamma_n = w $$

• Let $\alpha_i$ be the tail of $\gamma_i$, and let $\gamma_i=x_i\alpha_i$.