For the first problem, anything that starts with an a
, or just b
, or anything that starts with a b
then not an a
:
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
a + b + aa(a + b)* + ab(a + b)* + ba(a + b)* + bb(a + b)*
From these, we discard those beginning with ba
, leaving
a + b + aa(a + b)* + ab(a + b)* + bb(a + b)*
Optionally we can compress the three terms beginning in a
by
a + aa(a + b)* + ab(a + b)* = a + a(a + b)(a + b)* = a(a + b)*
and a final grouping is possible
a(a + b)* + b + bb(a + b)* = (a + bb)(a + b)* + b
The solution in the OP isn't valid as it does allow ba
(choice b
in the parenthesis, then a*
once).
For the second problem, let us consider all strings with multiples of three b
's
(bbb)*
and let us insert abritrary strings of a
wherever possible: we get
a* (a* b a* b a* b a*)* a*
This solution is valid. Anyway, it leaves multiples possibilities for the decomposition of the initial and final strings of a
, because of sequences a*a*
. These can be avoided by the mergings a*a* = a*
, which give the unambiguous
a* (b a* b a* b a*)*
The solution in the OP isn't valid as is does not represent the strings without any b
, though they should be accepted.
Best Answer
One very straightforward approach to (a) is to begin by listing the $8$ binary strings of length $3$. Every string whose length is a multiple of $3$ must be formed by concatenating those strings. I’ll illustrate with strings of even length: any string of even length can be segmented into two-character chunks, each of which must be $00,01,10$, or $11$, so the binary strings of even length are described by the regular expression $(00+01+10+11)^*$. (You may use some other symbol than $+$ to indicate alternatives; common alternatives are $\mid$, $\lor$, and $\cup$.)
Problem (b) is a little harder. The condition says that if a string contains a $1$ at all, that $1$ must either be the last symbol in the string or be followed immediately by a $0$. Ignore for a moment the exceptional case of a final $1$; if we just require that every $1$ be followed immediately by a $0$, we’re allowing precisely those strings that can be built by concatenating $0$’s and $10$’s, i.e., the strings described by the regular expression $(0+10)^*$. We’d like to have all of those strings, but also all strings that consist of one of those followed by a single $1$; how can you modify or extend the regular expression to include the latter type as well as the former?