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, 2022 at 22:09
  • $\begingroup$ They don't always halt. Even $\epsilon$-NFAs don't always halt. $\endgroup$ May 6, 2022 at 12:13


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.