0
$\begingroup$

I'm having issues using the pumping lemma to prove $L_2 = \{a^ib^j \mid i > j \}$ is non-regular. It's obvious to know that the language is non-regular as there is no way of tracking $a^{i's}$ and $b^{j's}$

So I've done some digging. On page 2 here I found a proof. However, it doesn't make sense to me.

Here is the proof, I will list my understandings as we go through the proof:

Assume by way of contradiction that $L_2\in \mathrm{REG}$, then $L_2$ satisfies the conditions of the pumping lemma. Let $p > 0$ be the pumping constant. Consider the word $w = a^{p+1}b^p$.

Makes complete sense.

Clearly $w \in L_2$ and $|w| > p$, so according to the pumping lemma there exist $x, y, z ∈ Σ^∗$ such that $w = xyz,$ $ |xy| ≤ p,$ $ |y| > 0$ and for all $i ≥ 0$ it holds that $xy^iz ∈ L$.

Now if an $i$ is chosen to be $0$, this would conflict with $|y| > 0$? It seems it's using $L$ instead of $L2$. Is there a reasoning?

Since $|xy| ≤ p$, then $x = a^n, y = a^m$, and $z = a^kb^{p+1}$ such that $m + n + k = p$, and $m > 0$.

This makes sense to me, as $z$ is equal to the rest of the $a's$ not in $x$ and $y$ plus all the $b's$.

We pump with $i = 0$ and get the word $xz = a^nz = a^na^kb^{p+1}$. Since $m+n+k = p+1$ and $m > 0$, then $n+k < p+ 1$.


Now this doesn't make sense to me. Pumping down ridding of $y$ contradicts the $|y| > 0$ rule and how does $m+n+k$ change to now equal $p+1$

Thus, $xz \notin L_1$, in contradiction to the pumping lemma. So $L_2$ is not regular. Note that it is crucial to “pump down” for this language.

If you guys can help me understand this proof, that would be great thanks

$\endgroup$
1
$\begingroup$

Now if an $i$ is chosen to be 0, this would conflict with $|y|>0$?

Note it's $|y|>0$, not $|y^i|>0$, so there's no problem.

All your other confusions come from the typos in the proof. I rewrite the proof (the fixed typos are colored red) as follows.

... Clearly $w \in L_2$ and $|w| > p$, so according to the pumping lemma there exist $x, y, z \in \Sigma^∗$ such that $w = xyz,$ $ |xy| \le p,$ $ |y| > 0$ and for all $i \ge 0$ it holds that $xy^iz \in L$. Since $|xy| \le p$, then $x = a^n, y = a^m$, and $z = a^kb^\color{red}p$ such that $m + n + k = \color{red}{p+1}$, and $m > 0$. We pump with $i = 0$ and get the word $xz = a^nz = a^na^kb^\color{red}p$. Since $m+n+k = p+1$ and $m >0$, then $n+k \color{red}{\le p}$ ...

$\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.