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

Question

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 |Q_C|=1 ∧ |F_C|=0 ∧ δ_C(q_0C,0)=δ_C(q_0C,1)=q_0C

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.

Answer 1

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

Answer 2

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

Answer 3

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