[Math] Regular expression: At least two a’s and doesn’t end in bb

context-free-grammarregular expressions

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 string aaaaa has “at least two as and does not end in bb”, but your proposed expression does not match it, because every string matched by your expression will end with b.

I suggest you try it like this: If it doesn't end in bb it must end in one of ab, ba, or aa. (Or it could be shorter than 2 symbols, but if so it would fail to contain at least 2 as, 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 2 as and ends with aa”.

Then write a second expression for “contains at least 2 as and ends with ab”, and a third expression for “contains at least 2 as and ends with ba”.

Then the answer to your problem is just the union of the three expressions.

Do you think you can do that?

Related Question