1

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.$

amWhy
  • 209,954
ANDREA LUIGI PALLADINO
  • 25
  • 3

1 Answers1

0

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.

hgmath
  • 1,830