Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 5 down vote accepted

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?

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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