The Pumping Lemma: Examples

Consider the following three languages:

$$\begin{array}{lcrcl} L_1 & = & \{a^nb^n & \mid & 0\; \leq\; n... ...\ L_3 & = & \{a^nb^m & \mid & n,m\; \geq\; 0\} \\ \end{array}$$

The first language is regular, since it contains only a finite number of strings.

The third language is also regular, since it is equivalent to the regular expression (a*)(b*).

The second language consists of all strings which contain a number of `a's followed by an equal number of `b's.

Lemma: $L_2$ is not regular
Strategy: Proof by contradiction
Proof: Let us assume that it is regular; then we must have some set of strings of the form $\{xy^iz\; \mid\; i\, \geq\, 0\}\; \subseteq\; L$.
Suppose such a subset did exist.

-

Obviously, $y$ could not contain a mixture of `a's and `b's, since this would mean that $xy^iz$ would have `b's before `a's. Thus, $y$ must consist solely of `a's or solely of `b's.

-

Let us assume then that $y$ consists solely of `a's. Then if, for some $n$ we have that $xy^nz$ is in the language, there is no way that $xy^{n+1}z$ can be in the language, since this will contain extra `a's without any extra `b's. Thus there will be no way for $xy^iz$ to be in the language for every $i\, \geq\, 0$.

-

We can use exactly the same argument to refute the supposition that $y$ can consist entirely of `b's.

Thus we have shown that $y$ cannot consists of `a's `b's or their mixture; ie no such $y$ exists, and so the Pumping Lemma is not satisfied. Thus $L_2$ is not regular.
${\cal QED}$

(Note that we cannot draw any conclusions from the fact that $L_1 \; \subseteq\; L_2 \; \subseteq\; L_3$).