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??


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.

  • $\begingroup$ So that the proof is complete, I have to take all the three cases, right?? $\endgroup$
    – Mary Star
    Sep 5 '14 at 21:26

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$


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.


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.