# Making a NFA for accepting a string only if it contains the given substrings

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:

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?

• 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.
– Raphael
Jan 13 '18 at 14:04

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.
• 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? Jan 14 '18 at 17:10
• 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? Jan 14 '18 at 17:11
• 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 Jan 14 '18 at 17:22