2
$\begingroup$

Is there an efficient algorithm for minimizing a deterministic PDA in terms of states? Is it even computable?

I know that it is not possible to minimize a PDA in general, but my question is about deterministic PDA.

For tools like lexer generators, where occasionally a counter or a stack would be needed to lex languages with string interpolation or other constructs, the question for DPDAs would be interesting as well. The answer - and the algorithm - is well known for deterministic finite automata and to my knowledge, some lexer generator tools do utilize that.

Improve this question
$\endgroup$
4
  • $\begingroup$ There seems to be a misunderstanding. If you care about minimizing the number of states, it is possible to minimize a PDA: you can always translate the PDA into a PDA with a single state. See cs.stackexchange.com/q/37461/755. Do you really mean, minimize the number of states? $\endgroup$
    – D.W. ♦
    Commented Sep 12, 2022 at 20:48
  • $\begingroup$ Depending on the exact definition of "minimize", minimization seems like it might be decidable, given decidability of equivalence testing: en.wikipedia.org/wiki/… (namely, enumerate all "smaller" DPDAs, by whatever notion of "smaller" you use). Maybe you mean to ask whether there is an efficient algorithm? $\endgroup$
    – D.W. ♦
    Commented Sep 12, 2022 at 20:50
  • $\begingroup$ @D.W. Yes, I'm specifically asking for an efficient algorithm that could be applied to software mentioned in my OP. $\endgroup$
    – Peter Lenkefi
    Commented Sep 16, 2022 at 8:12
  • $\begingroup$ Please edit your question to correct the mistakes and to include all relevant information the question, so people don't need to read the comments to understand what you are asking. Thank you! $\endgroup$
    – D.W. ♦
    Commented Sep 16, 2022 at 18:02

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.

Browse other questions tagged or ask your own question.