Transforming a CFG into a PDA with single state

Question

Can I always transform a context-free grammar into a pushdown automaton with a single state? How can I do that? I cannot find any explanation how to do that.

Answer 1

The idea is really simple and well explain in wikipedia.

The intuition is that you use the stack in order to keep track of the word obtained with the CFG and to derive the word using left most derivation of the CFG.

For example if you have a rule $A\to BCaD$ in the grammar there is a rule in the automaton (with for only state 1) $(1,\epsilon,A,1,BCaD)$.

In other words if you read A at the top of the stack, you remove it and replace it by the four symbols $BCaD$ as if you used the rule of the CFG.

Notice that this rule is an expansion rule thus you use a $\epsilon$. Now in order to actually match the required word, when you see a letter in the stack you read it with the pushdown with for example this rule: $(1,a,a,1,\epsilon)$.

In other words, if you read a a at the top of the stack you remove it and accept as input a.

I hope it is clear.