Claim:  The language 

L = {w | w contains an equal number of 0's and 1's in any order.}

is not regular.

Proof:  We will use the Nonregular Language Theorem.  We must find an infinite
set S of strings such that the set S is pairwise distinguishable.

Let S = {w | w contains n 0's, n is any positive integer.}

(Comment:  Another way to write this is S = {0^n | n is any positive integer.}
0^n stands for a string of n 0's.)

Thus, S = {0, 00, 000, 0000, ...}

Clearly, S is infinite.  Now we must show that ANY pair of different strings 
chosen from S are distinguishable.  Let u = 0^i (that means i consecutive 0's)
and v = 0^j (that means j consecutive 0's) where i and j are different.
So, u and v represent two arbitrary strings in S.  To show that they are
distinguishable, we must find some string z that can be added to u so that
uz (u with z concatenated to the end of it) is in language L but vz is
not (or vice versa).  By choosing z = 1^i (that means i consecutive 1's)
we have uz = 0^i 1^i (i 0's concatenated with i 1's) which has an equal 
number of 0's and 1's and is thus in L.  However, vz = 0^j 1^i.  Since 
i is not equal to j, this string is not in the language.  Thus, we have shown
that any pair of arbitrary strings in S are distinguishable and S is infinite.
Thus, by the Nonregular Language Theorem, L is not regular.  Q.E.D.

---

Comments:

	1.  This proof is very similar to a proof that we saw in class.
	The fact that the 0's and 1's are in no particular order is 
	true, but in our proof we can choose any set S that is infinite
	and pairwise distinguishable.  It made things easier to choose
	the set S above.  The fact that we didn't consider all possible
	strings in L is irrelevant.

	2.  Other choices of S would have worked, but this one was
	easiest.

	3.  Q.E.D. stands for "quod erat demonstrandum" in Latin which means
	"which was to be demonstrated".  It is a common "end of proof" marker.