[Solved]: Regular expression for the language where every a is surrounded by b's

Problem Detail: 

I had a question on an assignment where we were supposed to write a regular expression for a language where every $a$ in $w$ is immediately preceded and followed by a $b$. My answer was $\epsilon + (b + bab)^*$. The teacher pointed out that my answer makes an $a$ surrounded by at least two $b$s, which isn't correct. I can't for the life of me figure out how to fix it to make it correct. Can anyone help?

Asked By : Bryan

Answered By : Yuval Filmus

Here is a regular expression for your language: $(b(ab)^*)^*$. It's not hard to check that every $a$ is bordered by $b$s in both directions. The other direction is more complicated and left to you.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/17924