1

{w : w has at least two a’s and an odd number of b’s}

I'm having trouble wrapping my head around how to get every single possible outcome based on this language. An odd number of b's is more or less ((bb)b), at least 2 a's is just aa(a*). I know this is not strictly relevant to the final regular expression, it's just how I'm thinking about the language.

Basically I can't figure out the expression for this language. If you need at least 2 a's, then I imagine you'd need 2 a's with no attached kleene star.

Additionally, how do you guarantee an odd number of b's without resorting to something like ((bb)b)?

Actually I can't even figure out where to start with this problem. Writing this question has confused me further.

EDIT:

I've thought of a possible solution:

(a+(bb)*b)*a(a+(bb)*b)*a(a+(bb)*b)*

but this is perhaps a little inelegant

pajkatt
  • 373
  • Think about $(bb)^ba(bb)^ba(bb)^*b$. – vadim123 Feb 07 '17 at 02:29
  • Yeah I just realized I could've done (a+(bb)*b)*a(a+(bb)*b)*a(a+(bb)*b)*. I think it looks right, just not sure. – pajkatt Feb 07 '17 at 02:31
  • your solution contains the word w=aa which isn't in the language. – dave Feb 07 '17 at 02:38
  • Maybe not elegant but easy to reason about: you could try to split into cases. you know that every w has two a's, take the first and the last one. now there are 3 places to fill (before the first a, in between, and after the last), think about all the possibilities that create a word with odd number of b's. – dave Feb 07 '17 at 02:47
  • it should lead to the following ugly solution: (bb)a(a+(bb))a(bb)b + (bb)a(a+(bb)b)a(bb) + (bb)ba(a+(bb))a(bb) + (bb)ba(a+(bb)b)a(bb)b – dave Feb 07 '17 at 02:52

0 Answers0