1
$\begingroup$

For this problem, I decided to tackle it by getting the intersection of the DFA that accepts binary strings of an even length and the DFA that accepts binary strings with an odd number of 1s (as seen below).

enter image description here enter image description here

What I'm having trouble with is taking the intersection of the two state diagrams, could I please have some help with this? Thank you!

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ There is a well known construction for this called the product automaton, here's a reference. $\endgroup$
    – Knogger
    Commented Apr 6 at 12:57

1 Answer 1

Reset to default
2
$\begingroup$

let's call first DFA A and second DFA B, let their corresponding states be A.Q and B.Q, then consider $A.Q$x$B.Q$ (cartesian product of states), you will get: $\{(q_e,q_0), (q_e,q_e), (q_0, q_0),(q_0, q_e)\}$, now let the new transition function for pair $\delta((a,b),w)$=$(A.\delta(a,w),B.\delta(b,w))$, so basically simulate both machine by tracking their states as a pair. now what will be the accepting state? we want both machines to be in accepting state, so our accepting state in this case will be: $(q_e,q_0)$ (notice pair's first component is state of first machine and second component state of second machine), thus first machine must be in $q_e$ to accept and second machine must be in $q_0$ to accept. In general accepting state can be expressed as $A.F$x$B.F$ (cartesian product of corresponding final states). now let's draw the diagram: enter image description here

Improve this answer
$\endgroup$

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.