2
$\begingroup$

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.

$\endgroup$

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Great !! So, can I positively assume that for FA accepting strings having a's divisible by m, and b's divisible by n, there ought to be mxn states in the minimal FA? $\endgroup$
    – Gaurav
    Feb 22, 2014 at 6:54
  • $\begingroup$ You don't have to assume anything. You can prove that it exists. If you're still unsure, you can try to construct the DFA directly (by following the product construction). $\endgroup$ Feb 22, 2014 at 7:08
  • $\begingroup$ Okay. I was just trying to memorize a few direct results so that they can help me in my exams. Thanks! :) $\endgroup$
    – Gaurav
    Feb 22, 2014 at 7:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.