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

CC BY-SA 4.0
2019-09-10T14:54:09.370Z
2019-09-10T14:54:09.370Z
J.-E. Pin
<p>In general, the size of the DFA that recognizes the intersection of <span class="math-container">$n$</span> languages is exponential in <span class="math-container">$n$</span>. 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.</p>

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

<p>Do these restrictions on the input languages eliminate the exponential lower bound?</p>

CC BY-SA 4.0
2019-05-14T16:46:15.460Z
Are $A_i$ and $B_i$ disjoint?
Gamow
CC BY-SA 4.0
2019-05-14T18:09:12.917Z
@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
CC BY-SA 4.0
2019-05-14T19:47:22.963Z
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
CC BY-SA 4.0
2019-05-14T20:00:44.013Z
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
CC BY-SA 4.0
2019-05-14T20:21:00.330Z
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
CC BY-SA 4.0
2019-06-02T05:39:01.200Z
Neat!  Without thinking too deeply into it, $O(2^n)$ sounds like it could possibly be an upper bound.
Michael Wehar
CC BY-SA 4.0
2019-06-02T05:44:24.000Z
What about determining if the intersection is non-empty?  How efficiently can we answer this question?
Michael Wehar
CC BY-SA 4.0
2019-06-02T05:49:42.713Z
Note: If for every $i$, $A_i \cup B_i = \Sigma$ and $B_i \neq \emptyset$, then the intersection is guaranteed to be non-empty.
Michael Wehar
CC BY-SA 4.0
2019-06-02T05:57:26.223Z
Maybe it's easier than I thought.  I'm thinking it can be solved in $\vert \Sigma \vert \cdot n^2$ time or possibly better.
Michael Wehar
CC BY-SA 4.0
2019-06-02T06:12:45.217Z
This is what I'm thinking.  Keep a list $S \subseteq [n]$ where $i \in S$ if $L_i$ has not yet been satisfied.  For every $x \in \Sigma$, go through each $i \in S$. 
 Check if $x \in A_i$ and if $x \in B_i$.  If for every $i \in S$, $x \in A_i \cup B_i$, then remove every $j$ from $S$ such that $x \in B_j$.  Repeat until $S$ is empty or every $x \in \Sigma$ fails to remove more elements from $S$.
Michael Wehar
<automata-theory><regular-language><dfa>
Complexity of DFA intersection in this specific case?
Display Name
# Complexity of DFA intersection in this specific case?

(Asked by: username_0 on 2019-05-14)

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?

**Tags:** automata-theory, regular-language, dfa
> **Comments:**
> **username_1**: Are $A_i$ and $B_i$ disjoint?  
> **username_0**: @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.  
> **username_1**: 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\}$.  
> **username_0**: 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.  
> **username_0**: 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.)  
> **username_2**: Neat!  Without thinking too deeply into it, $O(2^n)$ sounds like it could possibly be an upper bound.  
> **username_2**: What about determining if the intersection is non-empty?  How efficiently can we answer this question?  
> **username_2**: Note: If for every $i$, $A_i \cup B_i = \Sigma$ and $B_i \neq \emptyset$, then the intersection is guaranteed to be non-empty.  
> **username_2**: Maybe it's easier than I thought.  I'm thinking it can be solved in $\vert \Sigma \vert \cdot n^2$ time or possibly better.  
> **username_2**: This is what I'm thinking.  Keep a list $S \subseteq [n]$ where $i \in S$ if $L_i$ has not yet been satisfied.  For every $x \in \Sigma$, go through each $i \in S$.   Check if $x \in A_i$ and if $x \in B_i$.  If for every $i \in S$, $x \in A_i \cup B_i$, then remove every $j$ from $S$ such that $x \in B_j$.  Repeat until $S$ is empty or every $x \in \Sigma$ fails to remove more elements from $S$.  

---

## 1 answers

### Answer by username_3 on 2019-09-10. Score: 7 | Accepted answer

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$.


---

