HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Does a PDA immediately accept if at final state with empty stack?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
stackwithacceptemptypdafinaldoesstateimmediately

Problem

If computation on a PDA reaches a final state with an empty stack, will it immediately accept, regardless of whether or not the input tape has ended. For example if I have a PDA to recognize the language of strings where $a^nb^n$, if it was fed the string "aaabbba", will it stop after seeing the last "b" if the stack were empty and it was in an accept state? Or would the PDA, need to specify a dead state from the final state for incorrect strings?

For example, this PDA would seem to accept "aaabbba":

Solution

There are two ways in which a PDA may accept:

  • Final state: The PDA has finished reading the input and it is in the final state



  • Empty stack: The PDA has finished reading the input and its stack is empty.



The PDA in the example you have provided is non-deterministic, and when non-deterministic systems read an input for which a transition is not defined, they get stuck. In this case, when the PDA reads the string aaabbba, it would get stuck after reading the last b.

Context

StackExchange Computer Science Q#70985, answer score: 7

Revisions (0)

No revisions yet.