I've just started to learn about regular expressions and don't think I've got the hang of things at all. One of the problems I am looking at asks for a regular expression for all words over the alphabet {a, b} that contains at least two a's and doesn't end in bb.
So far I've got the following based on some other examples I found…
b*a(b*aa*(ba)*b)
Is this correct?
Best Answer
Your proposal,
b*a(b*aa*(ba)*b)
is not correct. For example, the stringaaaaa
has “at least twoa
s and does not end inbb
”, but your proposed expression does not match it, because every string matched by your expression will end withb
.I suggest you try it like this: If it doesn't end in
bb
it must end in one ofab
,ba
, oraa
. (Or it could be shorter than 2 symbols, but if so it would fail to contain at least 2a
s, so we can disregard this possibility.)If it ends in
aa
then what might the rest of the string look like? What restrictions are on it? Try writing a regular expression for “contains at least 2a
s and ends withaa
”.Then write a second expression for “contains at least 2
a
s and ends withab
”, and a third expression for “contains at least 2a
s and ends withba
”.Then the answer to your problem is just the union of the three expressions.
Do you think you can do that?