Given the following decision problem:
Input: Non-Deterministic PDA r that accepts via an empty stack
Output: Does r have the smallest number of states of all PDAs that accepts the language L(r) ?
Which class does this problem belong to ?
d. None of the above
I think we can enumerate all PDAs with less states than r, but comparing 2 CFLs isn't a decidable problem (at least due to my knowledge).
The correct answer is R, how can I compare those CFLs ?