# Build regular expression from language

I have the following language: L = {w $\in$ {a,b}* | aa is not part of w}. I have to construct a regular grammar from this language and I thought about first finding the regular expression from the language. I am not sure if my solution is a good one, so I thought about asking here.

The regular expression I found is: (b*abb*)*. Is this a good one?

-
Almost. You should have $a \in L$, but your expression does not allow for it. – dtldarek Dec 3 '13 at 10:04
Yes, you're right. I didn't notice that. Well, if I let go of the b, aa will be part of my language, which it isn't alowed to be. I guess this "(babb)* | a" solves the problem, isn't it? EDIT: in fact, b should be part of my language too. And b* also. So the answer should be (babb)* | a | b*. Am I right? – Jane Doe Dec 3 '13 at 10:11
Even closer. What about $ba \in L$? – dtldarek Dec 3 '13 at 10:22
Hmmm... just add (bba)? Because I need bbbababa too, for example. – Jane Doe Dec 3 '13 at 10:38
I think that would be enough. However, you could also simplify your expression. For example $(b^*a(b^*ba)^*|\varepsilon)b^*$ would take care of it all. – dtldarek Dec 3 '13 at 12:06

While looking for a regular expression for $L$ is a valid approach, since you ultimately want a regular grammar for $L$ an easier way in this case is to first construct a FA for the language (simple enough–one can do it with two states, both final) and use the FA to construct the grammar (even simpler–two variables and five productions).