-1
$\begingroup$

I am trying to design a DFA s.t. The set of strings in x ∈ {0, 1}∗ such that the number of zeros is a multiple of 3 and the number of one's is even.

My idea was to create two Machines M1 = (Q1, Σ, δ1, q1, F1), M2 = (Q2, Σ, δ2, q2, F2).

The first M checks if the number of 1's is even, and the second checks if the number of zeros is a multiple of 3.

If M1 accepts and M2 accepts, that is M1 intersection M2, then M accepts the input A. Is this a valid representation of a possible DFA, or am I supposed to make a singular Machine M s.t. the DFA accepts the input A?

$\endgroup$
  • $\begingroup$ You should try using the Cartesian product construction. It will allow you to build a new automaton based on M1 and M2's state diagrams. :) $\endgroup$ – Michael Wehar Jan 14 '18 at 18:22
  • 3
    $\begingroup$ In the future, please try CS Stackexchange for these non-research-level questions. $\endgroup$ – 6005 Jan 15 '18 at 4:59
1
$\begingroup$

Thanks to the hint given by @Micheal Wehar, I looked into Cartesian Product constructions and Intersections and I came across this answer:

https://stackoverflow.com/questions/7780521/how-to-use-the-intersection-construction-to-form-a-dfa

which seems to answer the question appropriately.

$\endgroup$
  • 3
    $\begingroup$ In the future, please try CS Stackexchange for these non-research-level questions. $\endgroup$ – 6005 Jan 15 '18 at 4:59

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