Math: Giving regular expression for a language:

Question

I am going over and learning regular expressions and languages. I was working through some questions about giving a regular expression to represent a specified language. The question I was a little stuck on is this:

Come up with a regular expression that expresses the following language. The alphabet of the langauge is {a,b}.

The language of all strings with two consecutive a's, but no three consecutive a's. (ie, "aa", "aabaa", "babaa" are in the language, while "abab", "aaaab" is not).

My answer for this so far is:

 (b*(e+a+aa)bb*)* (aa) (bb*(e+a+aa)b*)*

where 'e' is the empty string and '+' functions essentially as an 'or'.

I guess what I am wondering is if my answer is correct (I believe it is), and if it can at all be simplified?

Thanks guys.

Answer 1

I believe that your regular expression is correct. It ensures that an aa exists in the string, and makes sure that aaa cannot exist. As for being simplest (simplest being subjective here), I would say the following is simpler:

(b + ab + aab)* aa (b + ba + baa)*

Note that you could actually derive the above from the regular expression that you have. Taking just the part before the aa in your regular expression, we have:

  (b*(e+a+aa)bb*)*
= (b*bb* + b*abb* + b*aabb*)*
= (b + ab + aab)* 

That last step is a little bit of a jump, but it takes noticing that all those b*'s are redundant due to the * on the whole expression, and a b existing inside the brackets.

Answer 2

I think this regex matches your language as well:

^((ab|b)*aa(ba|b)*)*$