# Pumping lemma for $L=\{a^{p}b^{q} ∣ 0 ≤ p ≤ q\}$

Using the pumping lemma for $L=\{a^{p}b^{q} ∣ 0 ≤ p ≤ q\}$ I need to prove that $L$ is irregular. I already have proven the irregularity for $L=\{a^{p}b^{q} ∣ 0 ≤ p < q\}$.

I have a gut feeling that these proofs will be identical. Is this correct?

A short summary of what I think the proof would look like:

1) define a word $w = a^{m}b^{m}$ which should be in $L$ and $|w| \geq m$

2) pumping lemma makes $w = xyz, y \neq \epsilon, |xy|≤ m$

3) define $x$, $y$ and $z$ (important is that $y$ would only consist of $a$'s)

4) after pumping realise that the amount of $a$'s is not valid with the amount of $b$'s in the language

5) Q.E.D. (contradiction)

• What did you mean in 1)? Surely $|w|=2m?$ – saulspatz Mar 6 '18 at 3:53

## 1 Answer

Let $A = \{a, b\}$, $L_1 =\{a^{p}b^{q} \mid 0 \leqslant p \leqslant q\}$ and $L_2 =\{a^{p}b^{q} \mid 0 \leqslant p < q\}$. Then $$a^{-1}L_1 = \{u \in A^* \mid au \in L_1\} = L_2$$ It is known that any quotient of a regular language is again regular. Therefore, if $L_1$ were regular, then $L_2$ would also be regular. Since you proved that $L_2$ is not regular, you are done.