Is this the correct way to use the pumping lemma?

Question

I've been watching lectures from Coderisland on YouTube about finite state machines, DFAs and NFAs, and in one discussion he talks about how to use the pumping lemma to show how a language is not regular. I don't know quite how to apply the lemma and want to understand if I'm doing it right. If I had something like:

w = {aⁿb^k, n =/= k}

am I correct in that I can say that:

h = {aⁿb^{n + r}, r > 0} is a subset of w, and thus if I show by the lemma that h is not regular, that w must not be regular since h is a subset of w.

The way I would show this is as follows:

1. h = xyz
2. |xy| <= n
3. x = a^n-r
4. y = a^r
5. z = b^{n + r}
6. xyz = a^n-ra^rb^{n + r}
7. xy²z = a^n-ra^2rb^{n + r} = a^{n + r}b^{n + r}

Thus h cannot be regular since a^{n + r}b^{n + r} is not of the form {aⁿb^{n + r}, r > 0}, and since h is not regular w must not be regular, since h is an element of w.

Have I applied it correctly? I understand how to apply it for an easy language like {aⁿbⁿ}, because I can apply the lemma directly to this language, but the only way I could think of for my language was to create a subset that belongs to my language, and apply the lemma to that.

If I haven't applied it correctly, is there a way to show that my language is not regular (or regular), using another lemma, or perhaps with closure properties?

This is a really awesome topic, even if I don't understand the pumping lemma fully, I'm excited to explore it further!

Answer 1

There are two mistakes in your proof.

First, is the mistake in this statement of yours:

if I show by the lemma that h is not regular, that w must not be regular since h is a subset of w.

Because consider the language L = {aⁿb^m | n,m natural numbers} h is a subset of L, but clearly L is regular, as it can be represented by the regular expression a*b*.

But you're so close to the solution, in which actually you don't need to consider h. You should instead choose a string in w so that however you apply Pumping Lemma to it, you will always get a string which is not in w.

Now this is your second mistake in step 3 of your pumping lemma. In pumping lemma, we are to prove that "there is an element of that language, such that however you apply pumping lemma to that string, you will always get a string that is outside the language".

In your proof, you deliberately pick x = a^n-r, without explaining why it must be the case. There might be the case that actually x = a^n-2 for example. In this case, fortunately, you still have the same conclusion that it doesn't satisfy pumping lemma (and hence it's not regular) since by considering xy^r+1z you will definitely have more a's than b's.

---

One correct way to prove your problem is applying pumping lemma to it directly (there are other methods such as using complement, or intersecting it with a regular language and prove that the intersection is not regular), but for the purpose of explaining pumping lemma, I will show you how to apply pumping lemma for this language.

So, the problem states that we have w = {aⁿb^k, n=/=k} and we are to prove that it's not regular.

1. Now consider the string s = aⁿb^n!+n (that is, n number of a's followed by n factorial plus n number of b's). By pumping lemma, if w is regular, there should be xyz such that s = xyz, and that |xy|<=n.

2. Since |xy|<=n and that we have aⁿ at the beginning of s, then both x and y must contain only a's. Let y = a^m. We know that 1<=m<=n.

3. Now we have the difference between the number of a's and b's is (n!+n)-n = n!. This number is divisible by any number in the range 1 to n, inclusive. So we have n!/m is a whole number. Let q = n!/m.

4. Considering the string xy^q+1z, we have the number of a's as (n-m)+(q+1)*m = n-m+qm+m = n+qm = n+n!, which is the same as the number of b's. So xy^q+1z is not in the language w since number of a's is the same as the number of b's. Therefore the language w doesn't satisfy the pumping lemma.

5. Therefore w is not regular.

---

To address the question in your comment, prove using complement.

1. Suppose w is regular. Then the complement w' should also be regular.

2. But the complement w' = {aⁿbⁿ, n natural number} is not regular (you showed that already, right?).

3. Therefore w is not regular.