patternMinor
Does a PDA immediately accept if at final state with empty stack?
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":
For example, this PDA would seem to accept "aaabbba":
Solution
There are two ways in which a PDA may accept:
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.
- 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.