1
$\begingroup$

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":

Improve this question
$\endgroup$

2 Answers 2

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

In the PDA you have shown, there is no transition for PDA to go after reading aaabbb. Your PDA will not stop there, since you have still something to read (last b). There is no transition defined for that. Also, since the PDA has not finished reading the input (there is still a b left to read), the PDA cannot transition to final state because it needs an epsilon (empty string) to do that.

Hence i believe your statement "For example, this PDA would seem to accept "aaabbba":" is inaccurate.

For a PDA to accept, I agree with the answer by pranavashok.

Improve this answer
$\endgroup$

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.