[Solved]: What is the possible number of states in the DFA of intersection of two given FA?

Problem Detail: 

Consider a DFA over $a,b$ accepting all strings having number of $a$ 's divible by 6 and number of $b$ 's divisble by 8. What is the minimum number of states in the resultant DFA ?

This problem can be solved by assuming 2 DFAs. One accepting the number of $a$ 's divible by 6 and the other accepting with number of $b$ 's divisble by 8. And then taking intersection of them. So what will be the number of states in the resultant DFA?

I tried drawing the DFA accepting all strings having number of $a$ 's divible by 3 and number of $b$ 's divisble by 3, and found it to have 3x3 (9) states. Can I asssume the reuslt to be 48 states for this case? Can it be inferred that the for string accepting number of $a$ 's divible by $m$ and number of $b$ 's divisble by $n$ , there will be $mn$ states? Or I need to draw it by hand? Or anything other? Any subtle hint will be very helpful.

Asked By : Gaurav

Answered By : Yuval Filmus

The product construction shows that if $L_1$ is accepted by a DFA having $n_1$ states and $L_2$ is accepted by a DFA having $n_2$ states then $L_1 \cap L_2$ is accepted by a DFA having $n_1n_2$ states; browse back to the product construction to understand why. The resulting DFA need not be minimal even if the DFAs for $L_1$ and $L_2$ were (a trivial example is given by $L_1 = L_2$, assuming $n_1>1$). In your case, this means that if you can find a DFA for $\{w : 6\mid \#_a(w)\}$ having six states and one for $\{w : 8\mid \#_b(w)\}$ having eight states, then you can find a DFA for the intersection having 48 states.

Is this DFA minimal? You can use the Myhill–Nerode criterion to show that indeed it is: the 48 words $\{ a^i b^j : 0 \leq i < 6, \; 0 \leq j < 8 \}$ are pairwise incomparable.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/21918