I came across following problem:
Given single state non deterministic pushdown automata $M$, whether $L(M)=\Sigma^*$ is decidable?
Now I know
- for DPDA/DCFG/DCFL, universality problem is decidable.
- for NPDA/NDCFG/NDCFL, universality problem is undecidable.
However I am not sure whether the same problem is decidable or not for single state NPDA. I know for every NPDA, there is equivalent single state NPDA. So the language classes of NPDA and single state NPDA are equivalent. But does having single state restriction makes universality problem decidable? For example, if that single state is final state (for non final single state, the language will be empty), can we simply check if there is looping transition on that state labeled with all symbols in its alphabet $\Sigma$ and decide its universality. That is, if there are such transitions then its language is equivalent $\Sigma^*$. However if the looping transition is missing label even for a single symbol, then its not equivalent to $\Sigma^*$. If yes, does this means that universality problem of single state NPDA is decidable even though it is of same language class as NPDAs?