5
$\begingroup$

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
$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks a ton. Excellent answer, precise and replete with an example... $\endgroup$ – krypto07 Apr 16 '13 at 2:46
  • $\begingroup$ Although I think you meant leftmost when you wrote "the contents of the stack correspond to the part of the string not rewritten in a rightmost derivation" $\endgroup$ – krypto07 Apr 16 '13 at 3:00
2
$\begingroup$

Converting a CFG to PDA can be done with a PDA that has only 2 states, but indeed you will need to use epsilon moves, at least in the second state that performs the derivation of the word and compares it to the input (avoiding $\epsilon$-moves in the first state is trivial).

The reason you need $\epsilon$-moves, is to perform the derivation of the word over the stack without reading the input. for instance, if the grammar is something like $S\to A$, $A\to a$, then you need an $\epsilon$-move to perform the first transition on the stack, but for the second rule you don't need an $\epsilon$-move, as you can do this production only when the input is $a$.

In other words, if all your productions were of the form $$ A \to \alpha B_1 B_2 B_3$$ where $\alpha$ is a terminal and $B_i$ is a variable – you will be able to avoid $\epsilon$-moves.

But this is exactly Greibach's Normal Form. Since any CFG can be converted into Greibach's normal-form, you are done.

$\endgroup$
  • $\begingroup$ Does your PDA accept by final state or empty store? If by final state, could you please specify where the transition from the initial to the final state occurs? I've also edited the question to better describe my query $\endgroup$ – krypto07 Apr 15 '13 at 4:01
  • $\begingroup$ in what I had in mind, at the first state you just push $S\bot$ to the stack (of course, you need to make also one production, this is why $L$ doesn't accept the empty word), and in the next state you perform the productions. The second state must be final, and the PDA accepts by final state and emptying stack. I think it's possible to adjust the above idea to fit the edit you made in the question. The first state will do the productions, the other state will be final and you'll move there when the stack gets empty; that state will have no outgoing edges. no need for $\bot$ then, I think. $\endgroup$ – Ran G. Apr 15 '13 at 4:29
  • $\begingroup$ Note that once the transition to the final state $q_f$ has been made and if we have seen $w$ of the input so far, any string $w\alpha$ will also be in the language if you remain in $q_f$ after reading more of the input. So, I think your initial answer would be incorrect. But even now, once we have emptied the stack and read the entire input, how do we transition to the final state without an $\epsilon$-move?? or for that matter, know when the stack is empty so that we can make that transition... $\endgroup$ – krypto07 Apr 15 '13 at 4:49
  • $\begingroup$ It's possible because you never put terminals on the stack. Then, for a production $A\to a$ you will move to the final state. If the input is not done yet, the PDA "dies". $\endgroup$ – Ran G. Apr 15 '13 at 4:59
  • $\begingroup$ right, it must also empty the stack. $\endgroup$ – Ran G. Apr 15 '13 at 5:30

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.