1
$\begingroup$

First I'll introduce the problem with just two substrings. Say you are asked to construct a NFA which accepts the input string if it has both "bb" and "aba" as substrings.

The solution we came up with in class was that we'll make a NFA with multiple start states (a start state with $\epsilon$-transitions to each of our desired multiple start states). We'll have two cases, one where the substring "aa" occurs before the substring "aba" and one where the substring "aba" occurs before the substring "aa".

Following is the NFA diagram:

NFA Diagram

But the problem with that solution is that it doesn't generalize well (for example, now if I have to check that the given string contains 10 given strings as substrings, if I have to make a branch for every permutation, I'll have 10! branches).

Is there a simpler solution to this where the complexity of the NFA to be drawn does not increase as factorial of the number of substrings?

$\endgroup$
  • 2
    $\begingroup$ NFA for checking a finite list of conditions are notorious for blowing up. There may not be a way around it, unless you can "combine" the conditions somehow. $\endgroup$ – Raphael Jan 13 '18 at 14:04
2
$\begingroup$

Given an alphabet $\Sigma = \{\sigma_1,\ldots,\sigma_n\}$, let us consider the problem of matching all strings which contain all of the letters as substrings, i.e. all the strings $\sigma_1,\ldots,\sigma_n$ as substrings. An NFA with $N$ states accepting this language can be converted to a context-free grammar in Chomsky normal form of size $O(nN)$ (this is the total size of all rules). It is known that any context-free grammar in Chomsky normal form for this language must have exponential size $\tilde{\Omega}((3/2^{2/3})^n)$ (see Theorem 9 here; we gain a quadratic factor since our grammar is in CNF), and so $N = \tilde{\Omega}((3/2^{2/3})^n)$.

Note that this is only an exponential lower bound, whereas the obvious construction has factorial complexity. However, you can improve on this construction. Given $n$ words, the idea is to guess which $n/2$ words will appear first and which $n/2$ words will appear last, and to recurse on each half. We obtain the recurrence $$ T(n) = \binom{n}{n/2}\cdot 2T(n/2) \leq 2^n T(n/2). $$ Expanding the recurrence and using a trivial base case $T(1) = 1$, we get $$ T(n) \leq 2^{n+n/2+\cdots} < 4^n, $$ which is only exponential. In actuality, $T(1)$ is the size of the largest word to be matched, so the bound above should be multiplied by that.

$\endgroup$
  • $\begingroup$ If we are recursively guessing which $n/2$ will appear first and which will appear last, won't we end up deciding on a precise order? (i.e. in the fashion of mergesort). So then shouldn't the complexity be just $O(n)$ because we need to check for each substring, in that order? $\endgroup$ – Peeyush Kushwaha Jan 14 '18 at 17:10
  • $\begingroup$ Suppose $n = 4$ and $\Sigma = \{a,b,c,d\}$. Suppose I guessed that $\{a,b\}$ appear first and $\{c,d\}$ appear last. Have I fixed a precise order? $\endgroup$ – Yuval Filmus Jan 14 '18 at 17:11
  • $\begingroup$ But are we not doing this recursively? So if $T(4) = C(4,2) \cdot 2 T(2)$ means we'll guess $\{a,b\}$ appears first and $\{c,d\}$ last, and there is a $T(2)$ in the expression, then doesn't $T(2) = C(2,1) \cdot 2 T(1)$ mean we guess $a$ will appear first and $b$ last, and in the second call we guess $d$ will appear first and $c$ last? Therefore doing this recursively, we have indeed fixed the order $\endgroup$ – Peeyush Kushwaha Jan 14 '18 at 17:22
  • $\begingroup$ Yes, eventually we go over all orders, but we use fewer states. $\endgroup$ – Yuval Filmus Jan 14 '18 at 17:23
  • $\begingroup$ Perhaps what's confusing you is that my recurrence skips the part about matching the actual words, but this should make a big difference. $\endgroup$ – Yuval Filmus Jan 14 '18 at 17:24

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.