Convert Context Free Grammar to pushdown automata

Question

$S \to EFG \mid aSt$
$E \to aEb \mid \epsilon$
$F \to bFc \mid \epsilon$
$G \to cGt \mid \epsilon$

How should I convert the above context free grammar to pushdown automata? is there any rules or approaches that I should know?

Answer 1

One way is to first find an equivalent grammar $(A, V, P)$ in which all rules are of the form $T \to w$ with $w \in V^*$ or $T \to a$, where $a$ is a letter. It is easy to do by introducing a new variable $T_a$ for each letter $a$. In your case

$S \to EFG \mid T_aST_t$
$E \to T_aET_b \mid \epsilon$
$F \to T_bFT_c \mid \epsilon$
$G \to T_cGT_t \mid \epsilon$
$T_a \to a$, $T_b \to b$, $T_c \to c$, $T_t \to t$

One can now design a pushdown automaton with only one state $q$ that simulates the left derivations of this grammar. Its stack alphabet is the set $V$ of variables of the new grammar. There is one transition for each rule of the grammar. Each rule of the form $T \to a$ gives rise to a transition $T \xrightarrow{a} \epsilon$ ($T$ is popped) and each rule of the form $T \to w$ with $w \in V^*$ gives rise to an empty transition $T \xrightarrow{\epsilon} w$ (the symbols of $w$ are pushed).