Pumping up your language

A formal language can be shown to be non-regular using a theorem called the Pumping Lemma, which states that any string beyond a certain length which belongs to a regular language can be divided into three strings, where repeating the middle string produces another string in the language.  A similar theorem, the uvwxy theorem, does the same thing for context-free languages.
In the following, a string containing n 'x's will be represented as x(n), and the length of string z will be represented as |z|.

The pumping lemma states that for any regular (type 3) language, there is an integer m > 0 such that, for any string of length > m, the string may be expressed as xyz where |xy| < m, |y| > 0, and xy(n)z is in the language for any n > 0.

The pumping lemma can be used to prove that the language {a(n)b(n), where n > 0} is not regular.  Let w be a string in the language such that |w| > m (where m is from the pumping lemma) and let x, y, and z be the substrings of w from the pumping lemma.  Then, by the definition of the language, there is a k such that w = a(k)b(k).  There are three possible cases for y:

1. y = a(i):  Then xy(2)z = a(k + i)b(k), which is not in the language.
2. y = b(i):  Then xy(2)z = a(k)b(k + i), which is not in the language.
3. y = a(i)b(j):  Then xy(2)z = a(k)b(j)a(i)b(k), which is not in the language.

By the pumping lemma, if the language is regular, xy(2)z is in the language, which is a contradiction.  Therefore, the language is not regular.

Proof that a language is not regular using the pumping lemma must not assume any restrictions on m, or the starting position of y or z.  Any x, y, and z that conform to the definition of w must be covered by one of the cases. 

The uvwxy theorem states that for any context-free language (type 2) language, there is an integer m > 0 such that, for any string of length > m, the string may be expressed as uvwxy, where |vwx| < m, |vx| > 0, and uv(n)wx(n)y is in the language for any n > 0.