1
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 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$
    – Yuval Filmus
    May 6, 2022 at 12:13

0

Reset to default

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.