0
$\begingroup$

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.

$\endgroup$

1 Answer 1

0
$\begingroup$

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*$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.