Black Box Decision problem for NFA

Question

Suppose we are given an NFA $M$ (without $\epsilon$-transitions) that we only know the alphabet $\Sigma$ and the number of states $|Q|$ but we do not know any other details of the NFA. We want to develop a black box algorithm that can test if $L(M)=\Sigma^{*}$. My idea is that we can feed every string up to size $|\Sigma|^{|Q|-1}$, if every strings are accepted, then $L(M)=\Sigma^{*}$. Since all strings up to size $|\Sigma|^{|Q|-1}$ must go through every reachable state in $M$, if all of them get accepted then no matter what string is input, it will be accepted. Am I correct?

Answer 1

Ellul, Krawetz, Shallit and Wang construct in their paper Regular Expressions: New Results and Open Problems a regular expression of length $n$ (for infinitely many $n$) such that the shortest string missing from its language has length $2^{\Omega(n)}$. Since a regular expression of length $n$ can be converted to an NFA having $O(n)$ states, this gives, for infinitely many $n$, an NFA having $n$ states such that the shortest string not accepted by the NFA has length $2^{\Omega(n)}$.

Conversely, if an NFA having $n$ states doesn't accept all strings, then it must reject some string of length shorter than $2^n$. This follows from the pumping lemma once you convert the NFA to a DFA. Hence the construction in the paper mentioned above is optimal up to the constant in the exponent.

Answer 2

No, that is not correct. Consider the following NFA over the one-symbol alphabet $\Sigma=\{1\}$:

      ,-----------------------.
      |-----------.           |
      v           |           |
a --> b --> c --> d --> e --> f
|
V
g

Assume that all edges are labelled with the symbol $1$, except that the edges $a\to b$ and $a \to g$ are $\epsilon$-transitions. Assume that states $c,d,e,f,g$ are accepting states, and $a,b$ are non-accepting states. This NFA has 7 states. It also accepts all strings of length up to 6 (in fact, all strings of length up to 14). However, it does not accept the input $1^{15}$ (of length 15).

However, your method does work for a DFA. It just doesn't work for a NFA.

Answer 3

No, you need to search up to exponentially long strings. See this answer to a related question on cstheory.SE: https://cstheory.stackexchange.com/a/3502/2367