4
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ See also this answer on the same cstheory question mentioned in Hermann Gruber's answer. $\endgroup$ – Yuval Filmus Oct 2 at 22:19
1
$\begingroup$

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.

$\endgroup$
  • $\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
0
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ this is exponentially long... $\endgroup$ – Joe Oct 3 at 2:44

Your Answer

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

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