UoL CS Notes
Menu

CFG to PDA Conversions

COMP218 Lectures

Pushdown Automata Convention

When we have a sequence of transitions like:

stateDiagram
direction LR
q0 --> q01: x,a/b
q01 --> q02: epsilon, epsilon/c
q02 --> q1: epsilon, epsilon/d

Pop $a$ then push $b$, $c$ and $d$.

We will abbreviate it like this:

stateDiagram
direction LR
q0 --> q1: x, a/dcb

Replace $a$ by $dcb$ on top of the stack (notice: the reverse order: the first symbol of the word is at the top of the stack)

Converting a CFG to a PDA

The idea is to simulate the derivations.

We will convert the following context free grammar:

\[\begin{aligned} A&\rightarrow 0A1\\ A&\rightarrow B\\ B&\rightarrow \# \end{aligned}\]

This would produce the following PDA:

stateDiagram
direction LR
[*] --> q0
q0 --> q1:epsilon, epsilon/A$
q1 --> q2:epsilon, $/epsilon
q2 --> [*]
q1 --> q1:epsilon,A/0A1\nepsilon,A/B\nepsilon,B/#
q1 --> q1:0,0/epsilon\n1,1/epsilon\n#,#/epsilon
  • The first transition is the main production.
  • The middle is all productions and terminals.
  • The end is the empty stack.

We can then use this to match a given input string (00#11):

Stack Input Processed
$A  
$1A0  
$1A 0
$11A0 0
$11A 00
$11B 00
$11# 00
$11 00#
$1 00#1
$ 00#11

As only the empty stack remains, then the input is valid.

General CFG to PDA Conversion

stateDiagram
direction LR
[*] --> q0
q0 --> q1:epsilon, epsilon/S$
q1 --> q2:epsilon, $/epsilon
q2 --> [*]
q1 --> q1:epsilon,A/a1...ak\nfor every production A --> a1...ak
q1 --> q1:a,a/epsilon\nfor every terminal a