# Does this DFA have a solution?

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.

## 1 Answer

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?

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