Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

Thank you in advance.

share|cite|improve this question
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).

share|cite|improve this answer
You're right... it is easier this way. Thank you for your hint. – Jane Doe Dec 3 '13 at 22:12

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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