A "devilish" pumping lemma example similar 
to a problem on the homework:

L = { 0^s 1^t 2^u | s + t = u }

I.e., strings in 0*1*2* with the number of 2's, equaling
the number of 0's plus the number of 1's.

You want to prove that there cannot be a DFA with any finite number
of states which accepts the language L.

To do this, one uses the "Important Fact" I wrote in class:


IMPORTANT FACT:  If M is a DFA for L and M has p states, then
		 any string x of length at least p must create
		 a loop of length no longer than p in the graph of M
		 and the loop occurs in the first p letters of x.

We also have the resulting "pumpability" corollary:

COROLLARY:       If M is a DFA for L and M has p states, and
		 x is any string of length at least p
		 Then if x is in L, x can be written as x = uvw
		 (v is the loop) with v non-empty, |uv| <= p,
		 and for all n, uv^nw in L (v is pumpable).


So proving that a language is NOT regular can be done as follows:

   Show that no DFA can exist for L.

IE:

   For all numbers p no DFA can exist with p states.

Using corollary we get:

      For all numbers p, "COROLLARY" above cannot be true.

Expand this to:

for all numbers p,
  there is a string x in L,
    such that for expressions x = uvw with v non-empty and |uv| <= p
      there is an n >= 0 such that u v^n w is NOT in L.

This seems to be a difficult under-taking but maybe it's easier if you think
of at as a game with the devil.  Your goal is to defeat the devil and 
prove that a language is not regular.  The devil's goal is to stop you.

1. DEVIL:  Chooses a number p  (you have to be prepared for ANY p)
2. YOU:    Choose an x in L for that p
3. DEVIL:  Chooses u,v,w with x=uvw ...and other properties listed above
4. YOU:	   Choose n for which u v^n w is NOT in L.  YOU DEFEAT DEVIL!

The hardest intuitive part is the second line -finding the interesting 
unpumbaple pattern x.

So let's look at the language 

L = { 0^s 1^t 2^u | s + t = u }

1. DEVIL:  Chooses p. 

2. YOU:	Choose an umpumpable pattern x.  

Here's an idea that often works:

If you can find a string with a streak of length p at the beginning, 
the string may turn out to be unpumpable.

We want a long streak at least p letters long.  So try:

x = 0^p 1^p 2^(2p)


3. Devil chooses u,v,w with x = uvw and v non-empty and |uv| <= p.

4. You could try to look at every possible u, v combination that the
devil presented and show him how to pump v.  Or instead, you could notice 
that you've already TRAPPED the devil (that's where step #2 is so important).
I.e., since |uv| <= p, and x begins with p 0's, then u and v are made
up of 0's so that in fact u = 0^i and v = 0^j with i+j <= p and j > 0.
So x can be written in the form x = u v 0^k 1^p 2^(2p) 
where i+j+k=p.

Therefore, pumping v up in x results in the string:

u v^n 0^k 1^p 2^(2p) = 0^i v^(n*j) 0^k 1^p 2^(2p)

The number of zeros is:  i + (n*j) + k = i+j+k + (n-1)*j = p + (n-1)*j

The number of 1's is p and the number of 2's is 2p.

The number of 0's + the number of 1's is 2p + (n-1)*j.

The last number is supposed to equal 2p (the number of 2's) for the
string to be in L, but choosing any n other then 1 results in something 
different.

E.g., choosing n = 0 (pumping down) results in 2p-j != p
      choosing n = 2 (pump twice) results in 2p+j != p
      choosing n = 3 (pump twice) results in 2p+2j != p
etc.
(n=1 never works because pumping once is always the original string).