[Solved]: Regular expression - every b preceded and followed by an even number of a's

Problem Detail: 

I'm trying to write a regular expression over the alphabet $\{a, b\}$ for the language in which every $b$ is preceded and followed by an even number of $a$'s.

I think the regular expression should include something like $((aa)^*b(aa)^*)^*$ but I don't know how to extend it in order to get to the correct form. Can anyone help me by providing a step-by-step solution?

Asked By : Viktor E.

Answered By : jmite

The answer you already have covers almost all the cases: any time there's a $b$, there need to be an even number of $a$'s, so that covers all words containing a $b$.

However, there's an edge case where there are no $b$'s in your word, so you need to union your language with the case where the word has no $b$'s.

$((aa)^*b(aa)^*)^* \cup a^*$ should fit your final answer.

Best Answer from StackOverflow

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

3.2K people like this

 Download Related Notes/Documents