2

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.

Liam
  • 293
  • 1
    I understand this that an even number of $a$'s and odd number of $b$'s in any order are valid, e.g., $aabbababbbaabbb$ becasue that's six $a$'s and nine $b$'s – Hagen von Eitzen Feb 04 '17 at 20:40
  • @HagenvonEitzen that was my initial interpretation as well, but is that regular? – Liam Feb 05 '17 at 16:54
  • All somewhat feasible interpretations (either an even number of $a$'s or an odd number of $b$'s; an even number of $a$'s followed by an odd number of $b$'s; an even number of $a$'s mixed with an odd number of $b$'s) are regular and it is straightforward to write down automata. (The first interpretation needs five states, the others need four states) – Hagen von Eitzen Feb 05 '17 at 23:12

1 Answers1

2

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: enter image description here

Gerard Rozsavolgyi
  • 121
  • I have not seen "a modulo 2 calculus for number of a's or b's". Could you explain how you get the automata not using that calculus, please? Also, is this a deterministic or non-deterministic automata? I think it is deterministic. – manooooh Dec 07 '19 at 23:54
  • 1
    State 1 (initial) represents an even number of a's and b's, State 2 an odd number of a's, even b's, State number 3 even a's odd b's and State 4 odd a's and b's. Yes it's deterministic – Gerard Rozsavolgyi Dec 08 '19 at 08:43
  • Thank you!! Can you found the regular expression? Finding the equations for each state is not helpful since I could not isolate the variables. For example, $1=b3+a2$. – manooooh Dec 08 '19 at 15:23