In general, the size of the DFA that recognizes the intersection of $n$ languages is exponential in $n$. However, in my case I am computing the intersection of a very restricted subset of possible languages. I am curious if this weakens the lower complexity bound.

With an alphabet $\Sigma$, for the $i$th language, I have set $A_i \subseteq \Sigma$ and another set $B_i \subseteq \Sigma$. The $i$th language $L_i$ consists of strings containing any number of symbols in $A_i$, followed by one symbol in $B_i$, followed by any number of symbols in $\Sigma$. I would like to find a DFA that recognizes $L = L_1 \cap L_2 \cap ... \cap L_n$.

Do these restrictions on the input languages eliminate the exponential lower bound?

  • $\begingroup$ Are $A_i$ and $B_i$ disjoint? $\endgroup$ – Gamow May 14 '19 at 16:46
  • $\begingroup$ @Gamow I think it would recognize the same strings either way, because after one element from $B_i$ appears the rest of the string can be anything. Imagine dividing up the string into three parts, $a,b$ and $\sigma$, with each part being composed of symbols belonging to the subsets $A,B$ and $\Sigma$ respectively. Removing an element from $A$ that is in $B$ would make $b$ bigger and $a$ smaller in some cases, but the same strings would be recognized. $\endgroup$ – Display Name May 14 '19 at 18:09
  • 3
    $\begingroup$ What about the following situation: Let $\Sigma=\{a_1,\ldots,a_n\}$ be an alphabet of size $n$. Set all $A_i=\Sigma$, and set $B_i=\{a_i\}$. $\endgroup$ – Gamow May 14 '19 at 19:47
  • 3
    $\begingroup$ Oh, right, I see now. Your example is size $2^n$. (Edit: I tried to reduce the $n!$ original and I found out that it was shaped like a hypercube.) $\endgroup$ – Display Name May 14 '19 at 20:21
  • 1
    $\begingroup$ Neat! Without thinking too deeply into it, $O(2^n)$ sounds like it could possibly be an upper bound. $\endgroup$ – Michael Wehar Jun 2 '19 at 5:39

The precise bound is $2^n$. The lower bound was given in the comments: the state complexity of $A^*a_1A^* \cap \dotsm \cap A^*a_nA^*$ is $2^n$. For the upper bound, it suffices to observe that if $B$ and $C$ are subsets of the alphabet $A$, then the language $B^*CA^* = (B - C)^*CA^*$ is recognised by a 2-state DFA. It follows that the complexity of the intersection of $n$ such languages is upper bounded by $2^n$.


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.