2
$\begingroup$

I'm having a problem understanding this conversion. Let's say we have a CFL like this: $ { a^nb^m : n > m } $

A final state acceptance PDA for this language would push $A$ symbols in the stack for every 'a' input, and pop them for every 'b' input. If the stack has no more $A$s while we still have 'b' inputs to process, the automaton goes in a non-accepting state, and the string is not accepted.

To convert this to an empty stack acceptance PDA, I add the two states, one before the previous start state, and another state after the last to empty the stack. Whenever the inner automaton goes to the accepting state, it also moves to the empty-stack state with an $\epsilon$ transition.

If I test the string $aabbb$, after we process the first 3 characters, we still have an $A$ symbol in the stack, but the automaton moves to the empty-stack state with an $\epsilon$, it empties the whole stack, therefore the string is accepted.

Where is my mistake in this reasoning?

Improve this question
$\endgroup$
1
  • $\begingroup$ The constructions works the same for every automaton; why the concrete example? Have you checked the construction in your textbook? $\endgroup$
    – Raphael ♦
    Aug 6, 2015 at 10:16

1 Answer 1

Reset to default
3
$\begingroup$

Your description of the construction is wrong. The new automaton has a new initial stack symbol, from the new start state it places the original PDA's initial stack on top of it and moves to the original's start state. The new initial stack can only be removed in a new state that is entered via $\epsilon$ from final states, and in this new state all that is done is to slurp down the stack's contents.

This is activated from any final state, and the automaton can end up with empty input and empty stack only if the original reached the final state at the end of the input.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Yes, I know about the stack symbol, it just didn't seem important to mention in this case. So you're saying the the automaton ignores the $\epsilon$ transition to the empty-stack state (the new state) until there's no more input? $\endgroup$
    – devil0150
    Aug 5, 2015 at 22:30
  • $\begingroup$ @devil0150, no, it doesn't. Just that if the new PDA decides to slurp down its stack before ending the input, it will end up stranded with an empty stack in the middle of the input, and not accept. $\endgroup$
    – vonbrand
    Aug 5, 2015 at 22:34
  • $\begingroup$ Wouldn't that also happen after the 4th character of the string $aaabb$, which should be accepted? $\endgroup$
    – devil0150
    Aug 5, 2015 at 22:37
  • $\begingroup$ @devil0150, it can empty its stack, but not together with its input, and so does not accept. $\endgroup$
    – vonbrand
    Aug 5, 2015 at 22:38
  • $\begingroup$ So the converted automaton doesn't accept a string that the original one does? Or is the original automaton wrong? $\endgroup$
    – devil0150
    Aug 5, 2015 at 22:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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