0
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ 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). $\endgroup$
    – plshelp
    Oct 3, 2020 at 0:51
  • 3
    $\begingroup$ How to think on this? Try a few examples. Attempt a proof. Try to construct a counterexample. $\endgroup$ Oct 3, 2020 at 10:04

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Oct 3, 2020 at 11:27

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.