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.
$\begingroup$
$\endgroup$
2
-
$\begingroup$ Have you read the proof for the fact that PDA and context-free grammars are equally powerful? $\endgroup$– RaphaelCommented Jan 25, 2014 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$– RaphaelCommented Jan 26, 2014 at 14:38
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
0
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.
answered Jan 24, 2014 at 19:05
$\begingroup$
$\endgroup$
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).
answered Jan 24, 2014 at 23:11
$\begingroup$
$\endgroup$
Given some CFG with start S you want to be able to add the start S to the PDA's stack only once because if you "Push S onto the empty stack by empty transition to sef" then you can push infinetly many S which is no longer the same language. i.e. this wouldnt work : (q,ε,ε) ->(q, S)
So the trick is to have the transtion:
(q,ε,$) ->(q, SZ)
where $ is the start bottom stack symbol and Z is some dummy variable that will be used as the new bottom stack symbol. This disallows you from re-suing the above transition more than once. Now for every production A -> x where x can be any combination of symbols or variables you have:
(q,ε,A) -> (q,x)
For every symbol c you must also have: (q,ε,c) -> (q,c)
Lastly, a transtion to the accepting state q1 can be added
(q,ε,Z) -> (q1,Z)
Which enforces the stack to be empty before going to the accept state. This creates a PDA with two states for any CFG
