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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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?

Improve this answer
$\endgroup$
6
  • $\begingroup$ I tried the same before posting. I couldn't get it to work. I couldn't accept "acac". $\endgroup$
    – NeilPeart
    Dec 16, 2012 at 16:44
  • $\begingroup$ @Neil That should not be accepted, right? Because $b$ appears an even number of times. $\endgroup$
    – usul
    Dec 16, 2012 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, 2012 at 18:44
  • $\begingroup$ no. It is the conjunction ("and") of having the three conditions simultaneously. $\endgroup$
    – NeilPeart
    Dec 16, 2012 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, 2012 at 19:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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