Finite Automata and Regular Expression

Question

I'm stuck in writing a regular expression for a given language over the alphabet {a,b}. The strings are accepted if they start with the substring 'aa' or end with the substring 'bb.'

For example {aab, abb, aaba} are accepted but {Λ, ab, abaa} are not.

My attempted solution is: {aa* + ab* + bb*}, but I was thinking: what if the string started with a b? Then, my expression wouldn't work..

Any help would be great!

Answer 1

It is very simple:

Regular expression for language over the alphabet {a,b},string starts with sub-string 'aa' or ends with the substring 'bb'.

Regular Expression:

aa(a + b)* + (a + b)*bb

Note + is union here.

Answer 2

I think this will probably work.

^aa[a,b]*|[a,b]*bb$