Our book does a pretty good job with pumping lemma example, so I'm not going to completely rehash it here, but I will put up two examples we did in class that aren't directly in the book. First, let's recall the pumping lemma

Example 1: Balanced Parentheses

Let

\[ \Sigma = \{ (, ) \}, L = \{ s = \Sigma^* | {\text{s is a balanced set of parentheses}} \} \]

We can prove that L is nonregular by contradiction. Assuming L is regular, then the pumping lemma is true, and there exists a pumping length p satisfying the conditions spelled out in the lemma. If we can find a single string whose length is at least p that cannot be pumped (i.e. some xz, xyz, xyyz, xyyyz, etc is not in L) for any possible way of choosing x, y, and z, then we've shown that there is a logical condition, so the hypothesis can't be true.

In this example, let's choose the string (^p)^p; or, in other words, p left parentheses followed by p right parentheses. Condition 3 of the pumping lemma guarantees that y only consists of left parentheses, and condition 2 guarantees that len(y) > 0. If this is the case, then when we pump y, we only end up adding left parentheses without matching right parentheses, no matter which y we try to take. Therefore, we cannot simultaneously satisfy all conditions of the pumping lemma, so we've reached a logical contradiction assuming the language is regular, and so it must not be regular.

---

Example 2: A Tricky Language of 0s And 1s

Let's consider the following language now

\[ L_{neq} = \{ 0^n1^m, n \neq m \} \]

If we replace a ( with a 0 and a ) with a 1 in the last example, we've proven that the language

\[ L_{eq} = \{ 0^n1^n \} \]

Is nonregular. So it seems like maybe we can follow a similar proof. So again, let's assume by contradiction that L_neq is regular, at which point we apply the pumping lemma with an assumed pumping length p. Let's try the string

\[ s = 0^p 1^{p+1}\]

Knowing nothing about the DFA that would hypothetically recognize this language, other than the fact that it has p states, we would have to rule out every possible way of dividing up s into xyz in order to rule out the pumping lemma. Certainly, it is true that x and y consist only of zeros by condition 3 of the pumping lemma. And if we choose y = 0 (a single zero), we run into trouble by pumping one time to get 0^p+11^p+1, which is not in the language. So is that it? Have we found a string that can't be pumped? Unfortunately, no. There are other hypothetical ways of dividing the string up. If we let y have 2 or more 0s, then the string can actually be pumped. So we're going to have to get a little more creative.

Let's instead choose the string

\[ s = 0^p 1^{p+k}\]

where we leave k open, and we'll try to find a k that prevents us from dividing up the string in a way that it can be pumped. Let's represent symbolically all of the possibly ways the string can be split up as follows:

• x = 0^a
• y = 0^b
• z = 0^c1^p+k

Where a+b+c = p, and b > 0 by condition 2 of the pumping lemma; in other words, x and y are stuck in the 0s, y has at least a single 0, and z takes what's ever left of the 0s and all of the 1s. Now, when we repeat the string y x additional times, we get the string

\[ s = 0^{p+xb} 1^{p+k}\]

In other words, we add x*b zeros at the front of the string. Let's force the total number of 0s to be the same as the total number of 1s, so that

\[ xb = k\]

In this case, the string will not be in the language, so we've shown that it can't be pumped (i.e. condition 1 of the lemma is violated when we insist on conditions 2 and 3). In order for the above statement to be true, then the number of repetitions

\[ x = k/b\]

Should be a whole number. This wouldn't work for all b with the k = 1 that we started with. But how big does k have to be? Well, it should be divisible by all possible b values. From condition 3, we know that 1 ≤ b ≤ p, which means that any number between 1 and p needs to divide k. One number that will do this is

\[ k = 1 \times 2 \times 3 \times ... \times p = p!\]

Therefore, the string

\[ s = 0^{p}1^{p+p!}\]

Cannot be pumped, and we've arrived at a contradiction!

The easier way

The above approach required some imagination and creativity, but we can use some other facts about regular languages in our contradiction to make this proof much easier. In particular, if we assume that L_neq is regular, than its complement is also regular (recall how we construct a complement by flipping the accept status of every state in a DFA that recognizes the language). We also know that the intersection of two regular languages is regular (as you proved on homework 3). We can put these together to show that if we assume that L_neq is regular, then it must be true that

\[ \overline{L_{neq}} \bigcap \{ {0^*1^*} \} = {0^n1^n} = L_{eq} \]

is regular, where ⋂ means intersection and the overline means complement. But we've already shown that L_eq is nonregular, so we've reached a contradiction, and L_neq must also note be regular!