9
$\begingroup$

It is well known that the universality problem for NFA (deciding whether $L(A)=\Sigma^*$) is $PSPACE$-complete. However, what if every state of the NFA is known to be accepting? It seems to me that the problem is at most in $co$-$NP$, as a counterexample (unlike in the case of a general NFA) is polynomial (even linear) in the size of the input (the number of states). What is the complexity of this problem?

$\endgroup$
8
  • 1
    $\begingroup$ Unless there's a problem in my proof, it's very unlikely that your problem is co-NP because it'd imply that co-NP = PSPACE. Since a counterexample (i.e. a rejected word) could indeed be checked in time polynomial in its size, I'd be temped to say that there must be a problem in your proof that there is always a counterexample of polynomial size. Could you please explain how you would find such a polynomial size counterexample? The only thing I could think of was searching for a shortest path to a state in which the transition function isn't total but there could be another path that works... $\endgroup$
    – xavierm02
    Feb 10, 2017 at 14:29
  • 2
    $\begingroup$ It's not true that the shortest counterexample has polynomial size. Consider an NFA whose initial state is connected to cycles of lengths $2,p_1,\ldots,p_m$. You can arrange for the word $1^n0$ not to be accepted only if $n$ is odd and a multiple of $p_1,\ldots,p_m$. By choosing the $p_i$ to be the first $m+1$ primes, you obtain an NFA with $O(m^2\log m)$ states in which the shortest rejected word has length $e^{(1+o(1))m\log m}$. $\endgroup$ Feb 10, 2017 at 14:43
  • 1
    $\begingroup$ A simple reduction from SAT shows that the problem is indeed coNP-hard. The NFA branches into parts according to the clauses. Each part checks whether the input, which consists of an assignment followed by $\$$, satisfies the clause, and if so gets stuck at the final $\$$. This NFA is not universal iff the SAT instance is satisfiable. $\endgroup$ Feb 10, 2017 at 14:49
  • $\begingroup$ @YuvalFilmus You are correct regarding the counterexample, but as it turns out I misstated the problem. I know that $L(A)$ has no words with consecutive repeating letters, and I'm looking for universality with respect to all words with no consecutive repeating letters. Is there an exponential counterexample in that case, too? $\endgroup$
    – pron
    Feb 10, 2017 at 15:50
  • $\begingroup$ @YuvalFilmus In addition, the alphabet is no bigger than the number of states + 1. $\endgroup$
    – pron
    Feb 10, 2017 at 15:59

3 Answers 3

5
$\begingroup$

You problem is PSPACE-complete. I prove that it's PSPACE-hard by reducing universality of NFAs to universality of NFAs with all states accepting.


Let $A$ be a NFA. Add a new final state $q_\$$ to it and for every accepting state $q$, add a transition $q\overset{\$}{\to}q_\$$ where $\$$ is a fresh letter. For every letter $a\in \Sigma\sqcup \{\$\}$, also add a transition $q_\$\overset{a}{\to}q_\$$. And then make all states accepting. The new automaton accepts $L(A)\$ (\Sigma\sqcup \{\$\})^* \sqcup L'$ for some $L'\subseteq \Sigma^*$.

Now, add some automaton (with all states final) that recognizes the language $\Sigma ^*$ (i.e. the language of words that don't contain $\$$) in parallel. The new automaton will recognize $L(A)\$ (\Sigma\sqcup \{\$\})^* \sqcup (L' \cup \Sigma ^*)=L(A)\$ (\Sigma\sqcup \{\$\})^* \sqcup \Sigma ^*$.

Now, notice that we have $L(A)=\Sigma^*$ iff $L(A)\$ (\Sigma\sqcup \{\$\})^* \sqcup \Sigma ^*=(\Sigma\sqcup\{\$\})^*$. I.e. the process I described is a reduction from universality of a NFA to universality of a NFA with all states accepting. Since the reduction is polynomial, your problem is PSPACE-hard.

$\endgroup$
7
  • $\begingroup$ How do you construct an NFA for $\Sigma^* \setminus \Sigma^*\$$ all of whose states are accepting? $\endgroup$ Feb 10, 2017 at 14:32
  • $\begingroup$ Thank you, that's a nice reduction, and indeed answers my question. However, I had a different, more complex question in mind which I had thought I could reduce to this one, and @YuvalFilmus 's exponential counterexample made me realize that my own reduction was faulty, and I should have added the constraint that $L(A)$ does not contain words with repeated letters, and I'm checking for "universality" with respect to such words. $\endgroup$
    – pron
    Feb 10, 2017 at 15:43
  • $\begingroup$ @pron What do you mean by "word with repeated letters"? That $u=v_1aav_2$ or that $u=v_1av_2av_3$? $\endgroup$
    – xavierm02
    Feb 10, 2017 at 15:49
  • $\begingroup$ @xavierm02 The first one, i.e., no consecutive repeated letters. Is there an exponential counterexample in that case, too? $\endgroup$
    – pron
    Feb 10, 2017 at 15:50
  • $\begingroup$ @xavierm02 Also, the alphabet is no bigger than the number of states + 1. $\endgroup$
    – pron
    Feb 10, 2017 at 15:58
4
$\begingroup$

As mentioned in the comments, @xavierm02's answer has a bug. One can try and fix it, but here is a simpler construction [Kao, Rampersad, Shallit]. Given an NFA $A = (\Sigma, Q, q_0, \delta, F)$ with a single initial state, one can return the NFA $B$ that is obtained from A by turning all of its states to accepting states, and by adding #-labeled transitions from every state in F to the initial state $q_0$, where # is a new letter.

If $L(A) = \Sigma^*$, then it is easy to prove that $L(B) = (\Sigma \cup \{\#\})^* $. An accepting run of $B$ on an input $x$ with no #'s follows an accepting run of $A$ on $x$. Otherwise, we can write $x = z_1\cdot \# \cdot z_2 \cdot \#\cdots \# \cdot z_{n-1}\cdot \# z_n$, where all the $z_i$'s are words over $\Sigma$. Then, an accepting run $r$ of $B$ on $x$ operates as follows. Upon reading an infix $z_i$, $r$ follows an accepting run of $A$ on $z_i$, and then goes back to $q_0$ upon reading the next #.

Conversely, if $L(B) = (\Sigma \cup \{\#\})^*$, then in particular for all words $x$ over $\Sigma$, $B$ has an accepting $r$ run on the word $x\cdot \#$. Consider the last transition that $r$ traverses, it must be a transition of the form $\langle q_f, \#, q_0 \rangle$, where $q_f$ is some state in $F$. So, since non-# transitions in $B$ are transitions of $A$, then $r$ starts by following an accepting run of $A$ on $x$, and thus $x\in L(A)$.

$\endgroup$
0
$\begingroup$

It should be noted that Unary ($|\Sigma|=1$) all-accepting NFA universality becomes a Directed Graph cycle-detection problem and is in P

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.