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.
-
$\begingroup$ See also this answer on the same cstheory question mentioned in Hermann Gruber's answer. $\endgroup$ – Yuval Filmus Oct 2 at 22:19
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.
-
$\begingroup$ by NFA, I am talking about a NFA without $\epsilon$ transition.. $\endgroup$ – Joe Oct 3 at 2:44
-
1$\begingroup$ @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). $\endgroup$ – 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
-
1