# is it possible to minimize pushdown automata?

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?

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

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.

Sorry, minimize in terms of what?

Every PDA has an equivalent one having a single state.

• Huh, true. :) I guess "size of a reasonable encoding", e.g. the transition table. The other answers would work with that, wouldn't they? – Raphael Jan 21 '15 at 20:42

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.

• Note that this is state-minimal, but not transition minimal. As DW says, making it transition and state minimal is uncomputable. – jmite Apr 13 '15 at 12:17

"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: