0
$\begingroup$

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)

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.