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.
    Commented May 5, 2022 at 22:09
  • $\begingroup$ They don't always halt. Even $\epsilon$-NFAs don't always halt. $\endgroup$
    – Yuval Filmus
    Commented 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 you have read our privacy policy.