0
$\begingroup$

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?

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

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .