6
$\begingroup$

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?

Improve this question
$\endgroup$
10
  • $\begingroup$ Are $A_i$ and $B_i$ disjoint? $\endgroup$
    – Gamow
    Commented May 14, 2019 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
    Commented May 14, 2019 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
    Commented May 14, 2019 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
    Commented May 14, 2019 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
    Commented Jun 2, 2019 at 5:39

1 Answer 1

Reset to default
7
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.