5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Have you read the proof for the fact that PDA and context-free grammars are equally powerful? $\endgroup$ – Raphael Jan 25 '14 at 16:22
  • $\begingroup$ 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. $\endgroup$ – Raphael Jan 26 '14 at 14:38
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

Transforming a PDA into a CFG is hard, as we need to get rid of the states.

The converse, transforming CFG into single state PDA is straightforward, using an expand-match technique, see wikipedia. Single state when using empty stack acceptance. Two sates are necessary when transforming into final state acceptance (you need two to distinguish yes/no accepting, of course).

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.