Let Σ = {a, b}. Construct a regular expression defining each of the following languages over Σ.
(a) The language of all words that do not begin with ba
Answer: (a + b + ab + aa) a* b*
(b) The language of all words in which the total number of b’s is divisible by 3 nomatter how they are distributed, such as bbabbaabab
Answer: (a* ba* ba* ba*)*
For the first problem, anything that starts with an
a, or justb, or anything that starts with abthen not ana:a(a + b)* + b + bb(a + b)*In a systematic way:
If we expand all possible strings, making the first two symbols explicit, we have
From these, we discard those beginning with
ba, leavingOptionally we can compress the three terms beginning in
abyand a final grouping is possible
The solution in the OP isn't valid as it does allow
ba(choicebin the parenthesis, thena*once).For the second problem, let us consider all strings with multiples of three
b'sand let us insert abritrary strings of
awherever possible: we getThis solution is valid. Anyway, it leaves multiples possibilities for the decomposition of the initial and final strings of
a, because of sequencesa*a*. These can be avoided by the mergingsa*a* = a*, which give the unambiguousThe solution in the OP isn't valid as is does not represent the strings without any
b, though they should be accepted.