Show that the language is not regular using the pumping lemma.

Question

I have to show that the language $L = \{ a^k b^k \mid k > 0 \}$ is not regular using the pumping lemma.

I have done the following:

Let $i \geq 1$

$$x = a^i b^i \in L$$

$$|x| = 2i \geq i $$

Let $x = uvw$ with $v \neq \varnothing$ and $|uv| \geq n$.

Then $v = a^k$ for $ k \geq 1$.

So $uv^2w = a^{i+k} b^i \notin L$.

Therefore the language is not regular.

Is this correct?? Or is there a better way to formulate it??

Answer 1

There are three different possibilities for $v$:

1. $v = a^k, k \ge 1$, as you mentioned
2. $v = a^jb^k, j,k \ge 1$
3. $v = b^k, k \ge 1$

Your proof only covers case 1, but not the other cases.

Answer 2

It's almost correct; you just need to clarify what $i$ and $n$ refer to, use more words, and fix a few typos. Here's a cleaned up version:

---

Suppose instead that $L$ is regular. Then let $i \geq 1$ be the pumping length given by the Pumping Lemma and consider the string $x = a^ib^i$. Certainly, we know that $x \in L$ (just take $k = i > 0$) and that $|x| = 2i \geq i$. Hence, by the Pumping Lemma, we have $x = uvw$, where $|uv| \leq i$ and $v \neq \varepsilon$ and $uv^jw \in L$ for all $j \geq 0$. But then we know that $v = a^\ell$ for some $\ell \in \{1, \ldots, i\}$. Now take $j = 2 \geq 0$ and consider the string: $$ uv^2w = a^{i+\ell}b^i $$ which should be in $L$. But this is impossible, since $uv^2w$ contains $\ell \geq 1$ more $a$'s than $b$'s. So $L$ is not regular, as desired. $~~\blacksquare$

Answer 3

A more easy-to-understand (not as mathematical) explanation:

There are 3 possible cases for $v$:

1. $v$ lies before the transition from $a$'s to $b$'s. [ex: aa*aa*abbbbb]
2. $v$ lies in the transition from $a$'s to $b$'s. [ex: aaaa*ab*bbbb]

3. $v$ lies after the transition from $a$'s to $b$'s [ex: aaaaabb*b*bb]

   • For the first case, if you pump on $a^k$, it is evident that there will be more $a$'s than $b$'s, and thus $a^kb^k$ is not satisfied. [ex. aa aa aa abbbbb, there are more a's than b's]

   • For the second case, if you pump on $a^mb^n$, then you will break the order of $a^kb^k$. In other words, at some point, you will have an $a$, athen a $b$, then another $a$, then another $b$, which is not in the form $a^kb^k$. [ex. aaaa ab ab bbbb, there are the same number of a's and b's, but it is not in the form $a^kb^k$, and thus not in the language.]

   • For the third case, it is like the first case - if you pump on $b^k$, there will be more $b$'s than $a$'s, and thus is not a part of the language $a^kb^k$. [ex. aaaaabb b b bb, there are more b's than a's]

Because all possible pumping cases thus yield strings that are not in the language, we have shown that the language is not regular.