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
0 comments:
Post a Comment
Let us know your responses and feedback