6

I am trying to write a regular expression for the set of all strings in $\Sigma^*$ that starts with an even number of $b$'s and contains at most two $a$'s. The language contains only $a$'s and $b$'s.

This is what I have figured out so far:

$b^*$ - language with exactly $0$ $a$'s;

$b^*ba^*$ - language with exactly one $a$;

$b^*ba^*ba$ - language with exactly two $a$'s;

$bb^*$ - language starting with an even number of $b$'s.

I'm not sure where to go with this (or if how I have defined the language starting with an even number of $b$'s right). Can anyone help point me in the right direction?

J.-E. Pin
  • 38,183
  • 3
  • 33
  • 84
Sarah
  • 263
  • 1
  • 3
  • 10
  • Does your alphabet only contain $a$ and $b$? – J.R. Feb 18 '14 at 23:33
  • Yes it does, sorry I will add it into the question – Sarah Feb 18 '14 at 23:34
  • 6
    Then in Perl syntax your regular expression is "(bb)*(ab*a?b*)?" – J.R. Feb 18 '14 at 23:36
  • I'm not sure what you mean by Perl syntax? I think I'm looking for (bb)*(b*)*(b*ba*)*(b*ba*ba) – Sarah Feb 18 '14 at 23:41
  • No, not really. Your regular expression matches for example the string "bbb" which doesn't start with an even number of b's. But thats just one of the problems it has. Look [here](http://perldoc.perl.org/perlre.html#Regular-Expressions) for what I mean by Perl syntax. – J.R. Feb 18 '14 at 23:43
  • 4
    in the syntax of regular expressions, the answer of TooOldForMath translates to $(bb)^*ab^*(a+\epsilon)b^*$ which is almost right, you might want to add $+(bb)^*$ at the end if it is allowed to have just an even number of $b$ and no $a$. – Denis Feb 18 '14 at 23:48
  • 3
    an other way to put it is $(bb)^*(\epsilon+ab^*+ab^*ab^*)$. – Denis Feb 18 '14 at 23:49
  • Thank you so much for all of the help! I have been so confused as to what the syntax is. In class I haven't seen the use of + so I have had a lot of confusion. – Sarah Feb 18 '14 at 23:54

1 Answers1

0

To avoid having this question eternally unanswered, here is the answer proposed by Denis in the comments: $$(bb)^*(\epsilon + ab^* + ab^*ab^*)$$

J.-E. Pin
  • 38,183
  • 3
  • 33
  • 84