1
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • $\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$
    – Joey Eremondi
    Commented Aug 21, 2015 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$
    – edvas
    Commented Aug 21, 2015 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. ♦
    Commented Aug 21, 2015 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$
    – edvas
    Commented Aug 21, 2015 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. ♦
    Commented Aug 22, 2015 at 21:50

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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