Is my grammar for the language $L=\{w \in \{a,b\}^+ \mid w\text{ contains }aa\text{ followed by }bb\}$ correct?

Question

Consider the language $L=\{w \in \{a,b\}^+ \mid w\text{ contains }aa \text{ followed by }bb\}$.

I wanted to know if this grammar is correct or not.

This is my solution:

$S\to IaabbI.$

$I\to aI|bI|e.$

Answer 1

In my opinion the definition "$w$ contains $aa$ followed by $bb$" is somewhat ambiguous: Does it mean,

• $aa$ is immediately followed by $bb$ (i.e. the word must contain $aabb$)
• $aa$ is followed by $bb$, but there can be something in between? (e.g. $aababb$)

According to the first interpretation, your grammar is correct.

According to the second interpretation, we should use the rule $S\to IaaIbbI$ instead.