# Pumping Lemma - Grammar - Regular language

I'm having a bit of trouble understanding this exercise: Indicate whether the following grammar describes a regular language. Prove your answer.

G4: $$S \to aS|aSbS|ε$$

My answer is using this regular expression: $$L= \{a,ab\}^*$$ therefore, the grammar describes a regular language; The official solution says: Not regular. Use the pumping lemma and the string $$(a^p)(b^p)$$ and pump down. (where ^ means to the power of)

Can you help me understand why my regular expression doesn't work or why the pumping lemma proves the language is not regular?

• The language contains, eg, the string $aabb$, which is not in your regex. Commented Nov 4, 2019 at 17:12
• damn, I didn't even notice that. Thanks :) Commented Nov 5, 2019 at 8:36

Turning my comment into an answer: your regex does not give that grammar, but the following grammar: $$S \rightarrow aS \vert abS \vert \epsilon$$ This captures the iterative notion of the Kleene star; you can put either $$a$$ or $$ab$$, and at the end you can repeat that (or put nothing). Putting a string in the middle of the string (usually) cannot be expressed by just a Kleene star.
But as for proving it's not regular, note that any string in this grammar has at least as many $$a$$'s as $$b$$'s. The hint, then, tells you to pump the initial $$a$$ section down to get something for which this invariant does not hold. The exact argument requires just a bit of finagling with the specifics of the lemma.