Can’t a PDA get stuck in a cycle of blank transitions?

Should the implementation detect such cycles and do something about them? That seems quite complex to consider all the edge cases.

Does the answer vary for nondeterministic PDAs?

  • 1
    $\begingroup$ Have you checked posts about "PDA halt? $\endgroup$
    – John L.
    May 5 at 22:09
  • $\begingroup$ They don't always halt. Even $\epsilon$-NFAs don't always halt. $\endgroup$ May 6 at 12:13


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.