Designing a PDA w/o $\epsilon$-moves and $\leq 2$ states to accept an $\epsilon$-free CFL by final state

Problem Detail: 

I understand that any CFL can be accepted by a PDA by final state or empty store but I have been rather stumped by this question. The question states that the PDA has at most 2 states. Clearly 1 will be the start state while the other will be the final state (they cannot be the same since otherwise the empty string will be accepted). My initial idea was to take a grammar for $L$ in GNF (Greibach Normal Form) (refer to Ran's answer below for details on how a CFG in GNF can be converted to a PDA having 1 state and no $\epsilon$-transitions that accepts by empty store) and then give a PDA for this that meets the specification. But the problem is that I cannot find a way to do this without having an $\epsilon$-move at the final step when I have to move to the final state after the stack is empty. Any help would be greatly appreciated.

The PDA can be specified as $M = (K, \Sigma,\delta, q_0, Z_0, \{q_f\} )$ where $q_0$ is the initial state, $Z_0$ is the initial stack symbol and $q_f$ is the final state. The exact question is

Show that if $L$ is a CFL and $\epsilon$ does not belong to $L$, then there is a PDA $M$ accepting $L$ by final state such that $M$ has at most 2 states and makes no $\epsilon$-moves.

Thus, the PDA should

1. accept by final state
2. have at most 2 states
3. make no $\epsilon$-moves

Asked By : krypto07

Answered By : Hendrik Jan

Indeed, as you say, a PDA can accept by final state or by empty stack. The two acceptance criteria can be effectively translated into one another. Main ingredient of that translation is to clearly mark the bottom symbol of the stack, so the PDA knows when the stack will be empty. In that way it will not accidently block or accept when not planned.

True, given a CF grammar you can construct a single state PDA, accepting by empty stack. In that simulation the contents of the stack correspond to the part of the string not rewritten in a leftmost derivation. If the CFG you start with is in Greibach Normal form, then the PDA can be constructed to be "real-time" i.e., it has no $\epsilon$-moves.

The point is to combine both ideas. Thus mark the last nonterminal. When it is removed (not replaced by another nonterminal), then move to the second state, the final accepting state (at the same time emptying the stack).

For the CFG from your example $S\to aSB, S\to aB, B\to b$ this can be obtained by changing the grammar a little and making a "marked" copy $\bar X$ of each nonterminal $X$ to indicate bottom of stack: $\bar S\to aS\bar B, \bar S\to a\bar B, \bar B\to b, S\to aSB, S\to aB, B\to b$. Production $\bar B\to b$ is the final one. $\bar S$ is the new start symbol.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/11321