Qfyilyi

I know that it isn't necessary that cross product automaton for two minimal DFAs be minimal, but according to my analysis, if two DFAs do not have any common string then their cross product of minimal DFAs would be minimal. What should I do to prove this?

No.

Counterexample:

Let alphabet $Sigma = left{ 0, 1 right}$, languages $L_1 = left{ w0 ,middle|, w in Sigma^ast right}$ (i.e. the last digit is $0$), $L_2 = left{ w1 ,middle|, w in Sigma^ast right}$ (i.e. the last digit is $1$). Note that $L_1 cap L_2 = emptyset$.

Then the following DFAs $M_1$ and $M_2$ are minimal for $L_1$ and $L_2$ respectively:

And the cross product of $M_1$ and $M_2$ (for the intersection of languages) is:

But this is not minimal for the empty language. A minimal DFA for the language is:

In fact, cross-product DFA of $M_1$ and $M_2$ recognizes an intersection of languages $L(M_1) cap L(M_2)$ (if a state of cross-product DFA is accepting when the original two states are both accepting on original DFAs). So in this case a generated cross-product DFA always recognizes the empty language. Since a minimal DFA for the empty language has only one state and cross-product DFA has ((#states of $M_1$) × (#states of $M_2$)) states, almost all cross-product DFAs are non-minimal.

_{Also, even though if you define a state of cross-product DFA is accepting when either of the original two states is accepting, the above $(L_1, L_2)$ is a counterexample. Since $L_1 cup L_2 = Sigma^ast$, the minimal DFA has only one state.}

No, the Cartesian product (a.k.a. cross product in the question) of two minimal automaton may not be minimal.

Here are two simple counterexamples.

Note that a DFA with only one state will either accept all words if its start state is also an accept state or accept no words otherwise.

Let alphabet $Sigma = left{ aright}$. Let $E$ be a minimal DFA such that $L(E)$ is not empty nor all words. The number of states in $E$ must be greater than 1. Let $O$ be a minimal DFA such that $L(O)$ is the complement of $L(E)$. The number of states in $O$ must be greater than 1.

An automaton $P$ which is an Cartesian product automaton of $E$ and $O$ must have at least 2x2=4 states.

Suppose $P$ is constructed for the intersection of $L(E)$ and $L(O)$, i.e. the empty language. Its equivalent minimal DFA has 1 state, the start state, which is not an accept state.

Suppose $P$ is constructed for the union of $L(E)$ and $L(O)$, i.e., ${a}^*$. its equivalent minimal DFA has 1 state, the start state, which is also an accept state.

Please note the Cartesian product automaton of two DFA is not defined uniquely usually since it is allowed to choose different sets of accept states. This is the implicit view as in the book Introduction to the theory of computation by Michael Sipser.

Let $Q_A,Q_B$ be the number of states in $A,B$, respectively. The number of states in the product automaton is $Q_A Q_B$. Since $L(A) cap L(B) = emptyset$, the minimal automaton for $L(A) cap L(B) = emptyset$ contains a single state. This can only happen if $Q_A = Q_B = 1$, in which case $A,B in { emptyset, Sigma^* }$. We conclude that the product automaton is minimal exactly in the following three cases:

1. 
   $A = B = emptyset$.


2. 
   $A = emptyset$, $B = Sigma^*$.


3. 
   $A = Sigma^*$, $B = emptyset$.