I'm having trouble understanding the wording of one of my homework questions. Since this question appears early in the chapter, I have a feeling that I'm misinterpreting it.
Give a finite automaton that that accepts the following language: The language over $\{a, b\}$ of any even number of $a$'s and any odd number of $b$'s.
I'm having trouble with the usage of "and". Is it asking for an FA that accepts any string that is either an even number of $a$'s or an odd number of $b$'s, e.g. $aa$, $bbb$, $aaaa$, etc, but not accept strings like $aabbb$, $abbab$.
Or, is it asking for an FA that accepts any string that contains an even number of $a$'s or an odd number of $b$'s, e.g. $aabbb$, $ababb$, etc.
The first case is relatively simple, but I've been struggling with the second. I haven't even managed to convince myself that it is a regular language (because I haven't been able to come up with a regular expression that matches it).
My questions: Which interpretation seems most likely. Is the second case a regular language, if so, give a regular expression that recognizes it.
Best Answer
The second interpretation seems adequate here like the comment mentionned it. It's not very difficult though if you consider a modulo 2 calculus for number of a's or b's. There are only four possibilities so a four state automata is perfect to do the job: