1
$\begingroup$

My assignment asked to design a DFA that computes the language:

$L = \{ w \in \{a,b,c\}^\star | \#_a(w) $ is even, $\#_b(w)$ is odd, $\#_c(w)$ is even}

I have been stuck on this question for 2 hours, I draw approximately 20 sketches but still fail. The only thing that I observed so far is we need at least 8 states, or maybe more. And if a non-accept state reads a letter to an accept state, then it must read the same letter back to the non-accept state, or vice versa.(to keep the property of even or odd numbers) But I'm failing to handle all the cases, such like I can handle aabcc, ccbaa, but fail to abcbbca or abcbbac. Any suggestions?

$\endgroup$
2
  • 1
    $\begingroup$ You need exactly 8 states, storing the parity of the number of a's, b's, c's seen so far (separately). Keep going at it. $\endgroup$ Commented Feb 4, 2020 at 4:04
  • $\begingroup$ I'm still struggling, I think I really missing something here. I understand each state counts the number of a's,b's and c's. So that only even a's, odd b's and even c's is an accepted state. But it's still hard to draw the diagram. $\endgroup$
    – hh vh
    Commented Feb 4, 2020 at 4:42

1 Answer 1

3
$\begingroup$

As mentioned in the comments, you’ll need 8 states exactly. I like to label my states with semantic meanings, so in this case I’ll use a 3-digit number where each digit represents the number of as, bs, or cs we’ve seen ($\mod 2$).

Then we have all the states from $000$ to $111$ in binary.

You already know that $000$ is the start state and $010$ is the accept state.

All that remains are the transitions, which are independent of the accept rules at this point. From each state, there are 3 transitions: one for each of a, b, and c.

But now notice that for each letter, the corresponding transition is to the state with the corresponding bit flipped! For example, $110 \xrightarrow{a} 010$.

More mathematically, for any state $\alpha\beta\gamma$:

  • when we see an a, we go to the state $\alpha'\beta\gamma$, where $\alpha'$ is 1 if $\alpha = 0$, and vice versa;
  • etc., for the remaining letters.
$\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.