pushdown-automaton

Pushdown Automaton: Empty input versus empty stack


I have a theoretical computation science final coming up and while studying I got stuck on drawing pushdown automaton (PDA) diagrams.

The last transition is almost always

I understand this to mean consume none of the input string, pop the end of stack symbol and push nothing onto the stack.

Where I am stuck is this does not check that the input string is empty, just that the end of stack symbol in on the top of the stack.

For a language like 0n1n we push the end of stack symbol, then push a 0 every time a 0 is read from the input. On the first 1 we begin popping the 0s off the stack. In an ideal world once we get to the end of the input string the only thing on the stack will be the end of stack symbol and we can take that last transition. What happens if there are still 1s in the input. For example, an input string of 00111.

Couldn't we use the transition into the acceptance state while having remaining characters to consume?

Should there be a transition out of the final state, to some dead state, to account for remaining input characters?


Solution

  • For a language like 0^n 1^n we push the end of stack symbol, then push a 0 every time a 0 is read from the input. On the first 1 we begin popping the 0s off the stack.

    Correct so far.

    In an ideal world once we get to the end of the input string the only thing on the stack will be the end of stack symbol and we can take that last transition.

    It is not necessarily the case that there must be transitions at all in this case. It depends to an extent on how you're defining PDAs and how you would like your PDA to work. PDAs can typically accept by accepting state, by empty stack, or by both empty state and empty stack together. I prefer the last of these since it leaves the least to the imagination. They are all completely equivalent definitions in terms of computational power, however.

    What happens if there are still 1s in the input. For example, an input string of 00111.

    Good question. If you have 1s in the input after emptying the stack, the string is not in the language you're trying to accept anymore. At this point, you need to decide how you want to reject this input. One common method is to simply leave undefined the transition to take in such cases. When this happens and input remains, the machine is said to "crash" and, by default, it fails to accept the input. Another option, as you might be suggesting, is to add a new "dead" state to explicitly encode the operation of exhausting any remaining input.

    Whether you need to have explicit dead states, and how you want to indicate acceptance by your PDA, are basically conventions that you are free to pick (or that are specified for you by your instructor).