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.
- The string much start with $ bb $ .
- 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)^* $$