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?

  • $\begingroup$ What makes you think the expression you have won't cover it? The only case I can see you missing is a word with an odd number of $a$s but no $b$s. $\endgroup$
    – jmite
    Aug 21 '15 at 21:18
  • $\begingroup$ @jmite I think I'm missing the cases in which I only have $a$'s, no mather if their number is odd or even. $\endgroup$
    – Viktor E.
    Aug 21 '15 at 21:22
  • $\begingroup$ This question seems to be covered by the combination of cs.stackexchange.com/q/1331/755 and cs.stackexchange.com/q/2016/755. Is there any reason why I should not close this question as a duplicate of one of those? $\endgroup$
    – D.W.
    Aug 21 '15 at 21:50
  • $\begingroup$ @D.W. I don't see how those two questions are similar to this one since I'm not trying to prove that my language is regular or to convert a finite automaton to a regular expression. $\endgroup$
    – Viktor E.
    Aug 21 '15 at 23:20
  • $\begingroup$ @Eduard, the first link explains how to build a NFA for the language; the second link explains how to turn the NFA into a regexp. $\endgroup$
    – D.W.
    Aug 22 '15 at 21:50

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.