# Construct a grammar for the language

How can I achieve this. Write a grammar for the language consisting of strings built only of the letters a and b. The strings may have any number of these letters, but the letter combinations bab must be in each string somewhere, and each string must start with a bb. For example, the strings bbababbbaa, bbbaaaababaa, and bbbab are in the language, while a, aabb, baaa, and bbba are not.

• Your language is regular. You can design an NFA for your language, and then convert it to a context-free grammar. – Yuval Filmus May 16 '19 at 20:05

1. The string much start with $$bb$$ .
2. There should at least one occurrence of the sub-string $$bab$$

Hence, the structure of the regular expression must be something like this: $$bb[some \: string]bab[some \: string]$$

and, we can define $$[some \: string]$$ something like this:

$$(a + b)^*$$

which means, there can be any number (including 0) of either a's or b's. Therefore, the final regex for the word is, $$bb(a+b)^*bab(a+b)^*$$

• Doesn't match $bbab$. – rici May 16 '19 at 20:32
• Thank you! I figured it out now. – Lizzy May 16 '19 at 20:46