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