# How to get 2-state PDA for CFG?

I'm studying for my Computing languages test and there's one idea I'm having problems wrapping my head around, as far as I know for any Context Free Grammar (CFG), we can design a 2-state Pushdown Automaton (PDA). I am however a little bit confused that why this is possible.

• Have you read the proof for the fact that PDA and context-free grammars are equally powerful? – Raphael Jan 25 '14 at 16:22
• Please don't edit away your question after answers were provided, that's just impolite. Note that, in case you want to cover your tracks after getting help on, say, an exercise problem, that a) all revisions are kept and b) we don't support such behaviour. – Raphael Jan 26 '14 at 14:38

Depending on your acceptance definition, you might be able to get away with only a single state. The basic idea is to keep the state information on the stack. The first thing you'd try is for each symbol on the stack to contain the "current state", i.e. each symbol is a tuple $(s,X)$, where $s$ is a state of the original PDA and $X$ is a stack symbol in the original stack alphabet. That way, the state information is stored on the stack. There is a problem here, however: if we pop $(s,X)$, we don't know what state the PDA should be in. For the solution, see these lecture notes. The construction heavily relies on non-determinism.