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 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 at 18:09
  • 1
    $\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 at 19:47
  • $\begingroup$ In that case, $L_i$ includes any string that contains $a_i$ somewhere. Now, consider $L'_i$, defined with $A_i = \Sigma - {a_i}$ and $B_i = {a_i}$. $L'_i$ would also include every string that contains $a_i$ somewhere. The intersections of the languages would be the same because the languages are the same. $\endgroup$ – Display Name May 14 at 20:00
  • 2
    $\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 at 20:21

Your Answer

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

Browse other questions tagged or ask your own question.