Hi,

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 ?

a. R

b. RE

c. co-RE

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 ?

Thanks