13
$\begingroup$

is it possible to minimize pushdown automata? If no, why? Is it because for minimization the equivalence classes need to have a finite index and we cannot guarantee that for CFG?

Improve this question
$\endgroup$
0

5 Answers 5

Reset to default
9
$\begingroup$

Unfortunately the problem is not computable. It is undecidable even to tell if two arbitrary PDAs are equivalent; minimizing a PDA is even harder.

Improve this answer
$\endgroup$
1
8
$\begingroup$

I answered basically the same question (put more generally) here.

The argument in short: if you could do this, you could decide universality, and a couple of other undecidable properties of PDA/CFG. Hence, by reduction, there can be no such minimizer.

Improve this answer
$\endgroup$
4
$\begingroup$

Sorry, minimize in terms of what?

Every PDA has an equivalent one having a single state.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Huh, true. :) I guess "size of a reasonable encoding", e.g. the transition table. The other answers would work with that, wouldn't they? $\endgroup$
    – Raphael
    Commented Jan 21, 2015 at 20:42
2
$\begingroup$

I don't know about minimizing in the way you do with non-pushdown automata, but...

You can convert a CFG to PDA right? And that conversion according to Hopcroft has only one state, which is very minimized dont you think? So, all you have to do, is, convert your PDA to CFG, and then your CFG back to PDA, you'll have a 1-state PDA.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Note that this is state-minimal, but not transition minimal. As DW says, making it transition and state minimal is uncomputable. $\endgroup$
    – Joey Eremondi
    Commented Apr 13, 2015 at 12:17
1
$\begingroup$

"minimize" typically means "global minimum" but sometimes can refer to a "local minimum" in which case there do exist heuristics ie strategies that can result in some reduction but not consistently find the global minimum. and also some special classes of PDAs can be minimized or "trimmed". "non guaranteed terminating" machine learning optimization algorithms eg genetic algorithms can be employed here also. here are two papers on "visibly push down automata" a subclass. 2 example papers along these lines:

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.