0

Find a finite automaton that recognizes the language $$L=\{w\in\{a,b\}^*\mid\text{$w$ has an odd quantity of $a$ and an even quantity of $b$}\}.$$ Indicate whether the automata is deterministic or not.

I tried to find a regular expression for $L$: $$(a(aa)^*+(bb)^*)^*$$ but then I realized that $\lambda\notin L$ since there is not odd quantity of $a$, so my final regex is $$(a(aa)^*+(bb)^*)^+$$ I am not able to find an automata for this language. I tried with:

My attempt

but if we call $z=a(aa)^*+(bb)^*$ then I am not able to graph $z^+$.

How can we get the automata?

manooooh
  • 2,269
  • Oh, this is not correct. We could have $ababa\in L$ but my regex does not include it. – manooooh Dec 06 '19 at 01:50
  • 1
    And on the other hand, your regular expression incorrectly accepts $abba$. – Daniel Schepler Dec 06 '19 at 01:54
  • 1
    My approach to constructing a finite state machine would be to let the states be members of $(\mathbb{Z}/2\mathbb{Z}) \times (\mathbb{Z}/2\mathbb{Z})$ corresponding to (number of $a$ mod 2, number of $b$ mod 2). – Daniel Schepler Dec 06 '19 at 01:55
  • I do not understand your approach. Why $\Bbb{Z}/2\Bbb{Z}={\overline0,\overline1}$ to both letters if one of them has to be odd/even? Could you detail your comment please? – manooooh Dec 06 '19 at 02:00
  • OK, for another hint: the initial state would be $(\bar 0, \bar 0)$ and the only accepting state would be $(\bar 1, \bar 0)$. – Daniel Schepler Dec 06 '19 at 02:08
  • @DanielSchepler so are you proposing a finite state machine of ordered pairs? – manooooh Dec 06 '19 at 02:38

0 Answers0