# What is the space in big-O notation of the minimal DFA accepting the intersection of two finite languages where their minimal DFAs are given

Given two minimal deterministic finite automatons called A and B where A accepts the finite language L(A) and B accepts the finite language L(B) and the alphabet of both languages and automatons are Σ={0,1}.

This implies that |Σ|=2.

Because that both A and B are minimal, there is no possibility to remove any state and transition neither from A nor from B, so L(A) and L(B) are unchanged.

C is minimal deterministic finite automaton that accepts L(C), where L(C)=L(A)∩L(B)

This implies that L(C) is finite and their alphabet is Σ={0,1} as well.

Because that C is minimal if one of its states and transitions of C is removed then L(C)≠L(A)∩L(B) anymore.

Assume that |A| is the number of states of automaton A, |B| is the number of states of automaton B and |C| is the number of states of automaton C.

I already know that I can construct C as the product of A and B so L(C)=L(A)∩L(B), but then |C|=θ(|A|•|B|), but C is not necessarily m̲i̲n̲i̲m̲a̲l̲. The running time of the algorithm that constructs the product takes θ(|A|•|B|).

It is possible then to run Hopcroft's algorithm to minimize automaton C in running time of O(|C|•log(|C|)), so still L(C)=L(A)∩L(B) and after that |C|≤|A|•|B|.

Because that |C|=θ(|A|•|B|) before the minimization, then Hopcroft runs in:

O(|A|•|B|•log(|A|•|B|)).

So in total the running time to get the minimal automaton C, so L(C)=L(A)∩L(B) this way takes O(|A|•|B|•log(|A|•|B|)).

Let me know if there is more efficient, faster and better time complexity algorithm to achieve the same thing.

But my real question is what is the space of the minimal automaton C after all this?

I know that it is |C|=Ω(1) in the best case, when L(A)∩L(B)=∅, because minimal automaton that accepts the empty language, only needs one state, which is the starting state, not final and trap, i.e. the automaton remains in this state for each read character from the input tape.

In this case |QC|=1 ∧ |FC|=0 ∧ δC(q0C,0)=δC(q0C,1)=q0C

But of course that this case won't happen always, so I am asking what will be the largest space of automaton C in the worst case?

For sure |C|=O(|A|•|B|), but can it be any better?

I think that yes, i.e. |C|=O(|A|+|B|)

Because it is always true that |L(C)|≤|L(A)| ∧ |L(C)|≤|L(B)|, where |L(A)| is the cardinality of L(A) as a set of words/strings, |L(B)| is the cardinality of L(B) as a set of words/strings and |L(C)| is the cardinality of L(C) as a set of words/strings and |L(A)|, |L(B)| and |L(C)| are all finite natural numbers, because L(A), L(B) and L(C) are all finite sets of words/strings. So the cardinality of the language is the number of words/strings in that language as set of words/strings. So if |L(C)|≤|L(A)| ∧ |L(C)|≤|L(B)| then L(C) never has more words/strings than both L(A) and than L(B).

If L(C) is smaller language both than L(A) and L(B) and may have fewer/lesser words/strings, then the minimal automaton C doesn't need more states than the minimal automaton A and minimal automaton B, so I don't think that it is right that |C|=O(|A|•|B|) when A, B and C are minimal and L(C)=L(A)∩L(B), but what I said is not a proof.

I need a proof that this statement is correct or refutation that this statement is incorrect and wrong, but I don't know how to either prove it or refute it.

It should be noted that if minimal automaton C doesn't have more states than minimal automaton A and B then:

|C|≤|A| ∧ |C|≤|B| and thus |C|≤min(|A|,|B|).

Any help or directions?

EDIT: I have just found and discovered 1 hour ago that the length of each word in L(A) and L(B) are equal, i.e. ∀ w,x,y,z: w∈L(A) ∧ x∈L(A) ∧ y∈L(B) ∧ z∈L(B) then |w|=|x|=|y|=|z|, where |w| is the length of the word w, |x| is the length of the word x, |y| is the length of the word y and |z| is the length of the word z. Sorry that I didn't know this before.

I also want to know the relationship between |C| and (|A|,|B|) when |A|→∞ ∧ |B|→∞, i.e. both the number of states of automaton A and automaton B are going to infinity.

You don't have to delete anything, just edit your answers and insert html that shows that the claim remains true with the new assumption or it doesn't true with that assumption.

• I said that the minimal automaton C should have fewer states than A, not vice versa! – Farewell Stack Exchange Jul 9 '17 at 7:52
• Sorry. Let me try again. You are claiming that "If L(C) is a smaller language than L(A), then minimal automaton C has fewer states than A." That needs justification. I'm skeptical. It might be worth playing with some examples to see if you can find a counterexample. – D.W. Jul 9 '17 at 15:22
• My example already has the property that all words in $L(A)$ and $L(B)$ have the same length. So it refutes your conjecture $|C| \leq \min(|A|,|B|)$, and shows that you cannot improve the trivial bound $|C| \leq |A||B|$ by more than a multiplicative constant. – Yuval Filmus Jul 11 '17 at 7:16

Here is a concrete version of D.W.'s idea. Let $n$ be even, and consider the language $$C_n = \{ w^2 : w \in \{0,1\}^n \}.$$ (Note that $C_n$ is a language rather than an automaton as in the original post.)

The words in $\{0,1\}^n$ are all pairwise inequivalent, and so the DFA complexity of $C_n$ (the number of states in a minimal DFA for $C_n$), which we denote by $D(C_n)$, is at least $2^n$.

In fact, the NFA complexity of $C_n$ (the number of states in a minimal NFA for $C_n$), which we denote by $N(C_n)$, is also at least $2^n$. Indeed, consider any NFA for $C_n$, and let $\sigma(w)$ be the set of states reachable from the initial state upon reading $w$. It is not hard to check that $\sigma(w) \neq \sigma(w')$ for $w \neq w' \in \{0,1\}^n$, implying the lower bound.

On the other hand, we can write $C_n = A_n \cap B_n$, where $$A_n = \{ x \in \{0,1\}^{2n} : \mathsf{EVEN}(x) = w^2 \}, B_n = \{ x \in \{0,1\}^{2n} : \mathsf{ODD}(x) = w^2 \},$$ where EVEN and ODD extract the letters in even and odd positions, respectively. It is not hard to check that the DFA complexity of $A_n$ is $O(2^{n/2})$. This shows that $$N(C_n) = \Omega(D(A_n) \cdot D(B_n)).$$ In particular, since $D(A_n)$ is unbounded as a function of $n$, it follows that $$D(C_n) \notin O(D(A_n) + D(B_n)).$$ Indeed, given $n$, $D(C_n) \geq 2^n$ whereas $D(A_n) + D(B_n) = O(2^{n/2})$.

The same calculation also refutes your conjecture $D(C_n) \leq \min(D(A_n),D(B_n))$.

• Impossible, I mean this is incorrect for every A, B and C minimal DFAs, because I already said that when L(A) intersection L(B) = empty language, the minimal DFA C doesn't need more than 1 state to recognize the intersection in this case, because it is the empty language, so for each case, the right answer is |Q(C)|=Omega(1), where |Q(C)| is the number of states of automaton C. You could say that |Q(C)|=O(|Q(A)|X|Q(B)|), where |Q(A)| is the number of states of automaton A and |Q(B)| is the number of states of automaton B and X is the multiplication sign/symbol. – Farewell Stack Exchange Jul 10 '17 at 13:50
• I'm not sure what you mean by "impossible". I gave an example of two finite languages $A,B$ satisfying $N(A \cap B) = \Omega(D(A) D(B))$. You gave a different example in which $D(A \cap B) = 1$ although $D(A),D(B)$ could be arbitrary. There is absolutely no contradiction between these claims. – Yuval Filmus Jul 10 '17 at 15:18
• I think that what you have showed is that N(A intersection B) = O(D(A)D(B)), but not Omega, because product won't return more states than |A|X|B|, but maybe I am confusing with the functions 'N' and 'D' you are using in your answer. – Farewell Stack Exchange Jul 10 '17 at 18:25
• I gave an infinite set of pairs of languages $(A_i,B_i)$, whose DFA complexity tends to infinity, which satisfies $N(A_i \cap B_i) = \Omega(D(A_i) D(B_i))$. It's true that in general there is no meaningful lower bound, since as you said, $A,B$ could be disjoint. – Yuval Filmus Jul 10 '17 at 18:27
• I am not claiming that $N(A \cap B) = \Omega(D(A) D(B))$ for arbitrary finite languages $A,B$. I'm only claiming that there exists an infinite sequence of $A$s and $B$s for which this holds. In particular, this implies that it is *not* the case that $D(A \cap B) = O(D(A) + D(B))$. – Yuval Filmus Jul 10 '17 at 18:34

I don't have a complete answer, but I suspect the bound $|C| = O(|A| \times |B|)$ is tight -- I suspect we can construct a counterexample to your conjecture that $|C| = O(|A|+|B|)$, as follows.

If $x \in \{0,1\}^*$ is a string, let $\text{odd}(x)$ denote the bits at odd-numbered positions, and $\text{even}(x)$ the bits at even-numbered positions. For instance, $\text{odd}(01010) = 000$ and $\text{even}(01010) = 11$.

Fix an integer $n>0$. Let $S,T \subset \{0,1\}^n$ be two sets of $n$-bit strings. Define the languages

\begin{align*} L(A) &= \{x \in \{0,1\}^{2n} : \text{odd}(x) \in S\}\\ L(B) &= \{x \in \{0,1\}^{2n} : \text{even}(x) \in T\} \end{align*}

Then we have

$$L(A) \cap L(B) = \{x \in \{0,1\}^{2n} : \text{odd}(x) \in S, \text{even}(x) \in T\}.$$

If $S,T$ are "randomly chosen" subsets $\{0,1\}^n$, then on average we expect $A$ needs about $2^n$ states and $B$ needs about $2^n$ states, and it seems that the minimal DFA $C$ for $L(A) \cap L(C)$ will apparently need about $2^{2n}$ states. This is not a proof, but perhaps by choosing appropriate sets $S,T$ you can construct an explicit counterexample where $|C| \ge c \times |A| \times |B|$ for some constant $c>0$.

• |C|>=cX|A|X|B| is impossible, not even for c=1, because product NEVER returns automaton greater than |A|X|B|, I already said that the minimal automaton C should always satisfy |C|<=|A|X|B|. How did you come to |C|>=cX|A|X|B| for some constant c at all? – Farewell Stack Exchange Jul 9 '17 at 9:46
• @ErezZrihen, imagine $c = 0.1$. That would be sufficient to show that $|C| = O(|A|\times |B|)$ is tight. – D.W. Jul 9 '17 at 15:18
• Oh so when 0<=c<=1 then it is possible that |C|>=cX|A|X|B| of course. Okay thanks. It is a bit of disappointment that space of minimal intersection automaton must be no less than |A|X|B| on the worst case :( – Farewell Stack Exchange Jul 10 '17 at 1:11
• See my answer for an instantiation of this idea. – Yuval Filmus Jul 10 '17 at 18:45

The following solution is invalid. Step (3) is false. The minimal machine may not be a tree, though, as @YuvalFilmus notes, it is in general a DAG.

Furthermore, the supposed solution is a tree with all leaf nodes accepted. If they are all accepted and they all go nowhere, they are all equivalent (accepting $\epsilon$).

The key to this is that the languages $L(A)$ and $L(B)$ are finite.

1. Remove the (unique in a minimal DFA) rejection state, assuming that no transition implies rejection.
2. Then the minimal DFAs $A$ and $B$ have no cycles.
3. Furthermore, no state is equivalent to any state reachable from it, otherwise the language is not finite.

This implies that, given a binary alphabet,

• $A$ and $B$ are binary trees,
• rooted at the initial state,
• with (apart from the degenerate empty language) all leaf states accepted.

We can find a DFA $C$ that accepts $L(A) \cap L(B)$ by laying the two trees on top of one another, root to root, and collating them:

• A $C$ state is accepted only if both the corresponding $A$ and $B$ ones are.
• A $0$ or $1$ branch is developed in $C$ only if the corresponding branches exist in $A$ and in $B$.

The resulting DFA $C$ might not be minimal. The tree might have sterile branches that need pruning. For example, if all the words in $L(A)$ have even length, and all the words in $L(B)$ have odd length, none will coincide.

Thus the minimal DFA $C$ that accepts $L(A) \cap L(B)$ is no bigger than either, and can be discovered in similar time. $$|C| \le min (|A|, |B|)$$

• In general the graphs of $A,B$ are DAGs with out-degree at most 2. You can try your argument on the languages $L_A = 0\Sigma0\Sigma+1\Sigma1\Sigma$ and $L_B = \Sigma0\Sigma0 + \Sigma1\Sigma1$. You can check that $L_A,L_B$ are accepted by DFAs having 7 states (including the rejection state), whereas $L_A \cap L_B$ requires 10 states. – Yuval Filmus Jul 10 '17 at 18:40
• I know that and I admit that I didn't say this in my question, but if all words both in the finite languages L(A) and L(B) are equals in length, i.e. for each x, y where x in L(A) and y in L(A) then |x|=|y|, where |x| is the length of the word x and |y| is the length of the word y. Same for L(B), i.e. for each x, y where x in L(B) and y in L(B) then |x|=|y|, where |x| is the length of the word x and |y| is the length of the word y. Then this is the same for L(C), which is the intersection of L(A) and L(B). Is |C|<=min(|A|,|B|) true then? – Farewell Stack Exchange Jul 10 '17 at 19:03
• Your claim that $A,B$ are binary trees doesn't look right to me. For instance, consider the language $L_A = \Sigma 00000000$. The minimal DFA for that language is not a tree; it's a DAG. – D.W. Jul 10 '17 at 19:10
• I want to know if |C|<=min(|A|,|B|) is always true, if |A| and |B| are going to infinity. – Farewell Stack Exchange Jul 10 '17 at 19:26