# 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 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 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 at 19:47
• 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. – Display Name May 14 at 20:00
• 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 at 20:21