1
$\begingroup$

enter image description here

I'm trying to derive the language it represents. However, I'm kind of new to those topics. What happens if input b is gathered once or more than one time at state q without a in the stack? It does not have any transition, does it fail or since it is stuck is it accepted? example: abb

Improve this question
$\endgroup$
4
  • $\begingroup$ If all is well, your textbook defines PDAs, so you can look up what is supposed to happen. (Definitions may vary in different textbooks, so always look it up.) $\endgroup$
    – reinierpost
    Apr 26 at 22:02
  • $\begingroup$ checked it out, but couldn't find an answer to that. Presumably, it should fail $\endgroup$
    – mark
    Apr 26 at 22:44
  • $\begingroup$ We require you to credit the original source of all material that was originally written by others: cs.stackexchange.com/help/referencing $\endgroup$
    – D.W. ♦
    May 8 at 18:41
  • $\begingroup$ Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics. You can use LaTeX. $\endgroup$
    – D.W. ♦
    May 8 at 18:41

1 Answer 1

Reset to default
0
$\begingroup$

For many DFAs and PDAs, there is a computation path that will lead to a permanent reject state (and once computation reaches that reject state, any further transitions only return to that one state). For DFAs and PDAs that have such a state, these states (and all the transitions that lead to that state) are not shown in a diagram or are even left out of the transition description of such machines, with the understanding that there exists an implicit reject state.

For machines with an implicit reject state, any computational step that is encountered that is not explicitly described in the machine's definition is understood to just lead to the implicit reject state, never to be able to return back to acceptance. It can be thought of as a "crash" state or a "dead" state.

Improve this answer
$\endgroup$

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.