# minimum number of states in cross product of two minimum DFAs

If FA1 and FA2 are 2 DFAs with minimum number of states. I want to find cross product DFA (FA1XFA2). Will the cross product DFA obtained from 2 minimum DFAs also have minimum number of states(num of states in cross product DFA = num of states in FA1 x Num of states in FA2). How to think on this?

• Tip: construct an minimal automaton for $L = \{1^n|n\geq 0\}$ with $\Sigma = \{0,1\}$. The minimal automaton will have two states. Now cross the automaton with itself (both automaton are minimal) the result won't be minimal anymore (it only needs two states but has 4). Oct 3, 2020 at 0:51
• How to think on this? Try a few examples. Attempt a proof. Try to construct a counterexample. Oct 3, 2020 at 10:04

You probably know that if $$\cal A$$ and $$\cal B$$ are DFA, then their product recognizes the language $$L({\cal A}) \cap L({\cal B})$$. Now if $${\cal A} = {\cal B}$$, then $$L({\cal A}) \cap L({\cal B}) = L({\cal A})$$. Thus if $$\cal A$$ is a minimal DFA with at least two states, $${\cal A} \times {\cal A}$$ is never minimal.
• thank you sir. Understood now. I got this doubt when i was thinking to solve exercixe problem for binary number to be divisible by $2^k*m$, m is some odd number. I got k*m states from cross product dfa but then when i saw in answer of that qn, it is given as k+m. So i sensed that cross product dfa need not have min states. Oct 3, 2020 at 11:27