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$
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$
  • $\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 '14 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$ – Yuval Filmus Feb 22 '14 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 '14 at 7:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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