Finding a regular expression for a given language

Question

I'm told that given the alphabet {a,b}

I have to find the regular expression for a language that has at most two a's

I came up with this answer

$b^*$ U $b^*a$ $b^*$ U $b^*a$ $b^*$ $a$ $b^*$

So for the case with no A's, we can have any number of b's, for the case with 1 a, we have any number of b's followed by an a, followed by any number of b's. For the third case, we have exactly two a's.

Is this correct? Would this be a good way of going about solving these? Is there a general strategy to doing regular expressions?

Because my textbook gave me a completely different answer of:

$b^*(Є U a)b^*(ЄUa)b^*$

Where Є is the empty string, U is union (+).

Any input would be much appreciated.

Answer 1

Yes, your answer is correct. And so is the one from your textbook. They both generate the same language.

Basically, your answer has 3 cases whereas the one from your textbook only has 1 but more complex. The first case with no $a$ is the same as if the $Є$ was selected in both parenthesis.

First case with $b*$

$b∗(ЄUa)b∗(ЄUa)b∗ $

$=b*(Є)b∗(Є)b∗ $

$=b*b*b*$

$=b*$

Second case with $b∗a b∗$

$b∗(ЄUa)b∗(ЄUa)b∗ $

$=b∗(a)b∗(Є)b∗ $

$=b∗ab*b∗ $

$=b∗ab∗ $

And third case with $b∗a b∗ a b∗$

$=b∗(ЄUa)b∗(ЄUa)b∗ $

$=b∗(a)b∗(a)b∗ $

$=b*ab*ab∗ $

Note that $b*b*$ is essentially the same as $b*$.