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?

  • 1
    $\begingroup$ It's not just that for every NPDA, there (magically) exists an equivalent single state NPDA. You can actually compute it. So that if you can decide something about the language of single state NPDA, then you can also decide it for all NPDA: You just compute a corresponding single state NPDA and rune your decision algorithm on it. $\endgroup$ – xavierm02 Dec 24 '17 at 16:52
  • 1
    $\begingroup$ @xavierm02 Make an answer? $\endgroup$ – Yuval Filmus Dec 24 '17 at 18:18
  • $\begingroup$ @xavierm02 If I get it correct, you mean that the said problem stays undecidable, even after restriction of single state on NPDA, right? $\endgroup$ – anir Dec 24 '17 at 19:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.