# Complexity of DFA intersection in this specific case?

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?

• Are $A_i$ and $B_i$ disjoint? – Gamow May 14 '19 at 16:46
• @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. – Display Name May 14 '19 at 18:09
• 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\}$. – Gamow May 14 '19 at 19:47
• 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.) – Display Name May 14 '19 at 20:21
• Neat! Without thinking too deeply into it, $O(2^n)$ sounds like it could possibly be an upper bound. – 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$$.