Problem Detail: 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.
Asked By : NeilPeart
Answered By : usul
This is doable with a DFA. Hint: We need to keep track of three things simulataneously:
- The parity of a’s (have we seen an odd or even number of a’s so far?)
- The parity of b’s
- The parity of c’s
So there are 8 possibilities for what we’ve seen so far:
- Even number of a’s, even number of b’s, even number of c’s.
- Odd number of a’s, even number of b’s, even number of c’s.
- Even number of a’s, odd number of b’s, even number of c’s.
- …
Does that help?
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/7429
