Converting a CFG to a PDA

Every CFG can be converted to an equivalent PDA. The constructed PDA will perform a leftmost derivation of any string accepted by the CFG.

Suppose we are given a CFG and let $T$ and $N$ be its sets of terminal and non-terminal symbols respectively. Let $S$ be the start symbol. Then we construct the PDA as follows:

• The input alphabet is $T$
• There are only two states, let us call them $P$ and $Q$, where
  • $P$ is the start state
  • $Q$ is the only final state
• The stack alphabet is $T \cup N$
• The transitions are as follows:
  • $(P,\varepsilon,\varepsilon) \mapsto (Q,S)$
  • For each grammar rule of the form $A \rightarrow \alpha$, there is a transition $(Q,\varepsilon,A) \mapsto (Q,\alpha)$
  • For each terminal symbol $\hbox{\lq }{a}\hbox{'}$, there is a transition $(Q,a,a) \mapsto (Q,\varepsilon)$