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?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ Can you give an example of a word in your language not covered by $(b + bab)^*$? (which is by the way equivalent to $\epsilon + (b + bab)^*$) $\endgroup$ – Yuval Filmus Nov 11 '13 at 20:00
-
$\begingroup$ I believe babab would not be accepted by that regular expression, but it should be. $\endgroup$ – Bryan Nov 11 '13 at 22:35
Add a comment
|
$\begingroup$
$\endgroup$
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.
answered Nov 11 '13 at 23:48
