patternMinor
is it possible to minimize pushdown automata?
Viewed 0 times
minimizepossibleautomatapushdown
Problem
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?
If no, why?
Is it because for minimization the equivalence classes need to have a finite index and we cannot guarantee that for CFG?
Solution
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.
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.
Context
StackExchange Computer Science Q#37461, answer score: 7
Revisions (0)
No revisions yet.