Search code examples
regexregular-languagedfanfa

Finite Automata and Regular Expression

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!

Solution

  • 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.