2
$\begingroup$

I am trying to create a DFA that can recognize strings with alphabet $\{a,b,c\}$ where $a$ and $c$ appear even number of times and where $b$ appears odd number of times.

I am wondering that this may only be expressed with other methods such as Turing machine or context-free languages.

You might find it fun to think of the solution.

$\endgroup$
5
$\begingroup$

This is doable with a DFA. Hint: We need to keep track of three things simulataneously:

  1. The parity of a's (have we seen an odd or even number of a's so far?)
  2. The parity of b's
  3. The parity of c's

So there are 8 possibilities for what we've seen so far:

  1. Even number of a's, even number of b's, even number of c's.
  2. Odd number of a's, even number of b's, even number of c's.
  3. Even number of a's, odd number of b's, even number of c's.
  4. ...

Does that help?

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I tried the same before posting. I couldn't get it to work. I couldn't accept "acac". $\endgroup$ – NeilPeart Dec 16 '12 at 16:44
  • $\begingroup$ @Neil That should not be accepted, right? Because $b$ appears an even number of times. $\endgroup$ – usul Dec 16 '12 at 18:43
  • $\begingroup$ In your original question, did you mean "the set of strings where either (1) both # of $a$s and $c$s is even or (2) # of $b$s is odd? $\endgroup$ – usul Dec 16 '12 at 18:44
  • $\begingroup$ no. It is the conjunction ("and") of having the three conditions simultaneously. $\endgroup$ – NeilPeart Dec 16 '12 at 19:27
  • $\begingroup$ OK, just making sure. So $acac$ shouldn't be accepted. And I think if you make one state for each of the 8 possibilities and draw the transitions/make the final states, it will work. $\endgroup$ – usul Dec 16 '12 at 19:57

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.