# Black Box Decision problem for NFA

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?

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.

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.

• by NFA, I am talking about a NFA without $\epsilon$ transition.. – Joe Oct 3 at 2:44
• @Joe, that's not in the question, so I'm not sure how I could have guessed that. Regardless, I think it is straightforward to modify my NFA to meet that requirement, by removing $\epsilon$-transitions (e.g., cs.stackexchange.com/q/16237/755). – D.W. Oct 3 at 2:55

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

• this is exponentially long... – Joe Oct 3 at 2:44