Consider a language such as the language of all strings with an even number of 0's and an odd number of 1. Two strings X and Y are said to be distinguishable if there is SOME string Z that you can attach to both of them such that XZ is in the language but YZ is not in the language. Notice that X and Y need not be in the language themselves!
For example, consider the language of strings with an even number of 0's and an odd number of 1's. In this language, the strings X=0 and Y=1 are distinguishable. Why? Because if we add the string Z=01 to both of them, we get XZ is 001 (which is in the language) and YZ is 101 (which is not in the language!).
So what? Well, the fact that 0 and 1 are distinguishable for this language means that any DFA for this language must end up in different states when run on 0 (beginning at the start state) and when run on 1 (beginning at the start state).
The Distinguishability Theorem says that if we can find a set of n strings (call the set S) such that every pair of strings in S is distinguishable, then the number of states in any DFA for this language must be at least n (the number of strings in S) simply because every pair of distinguishable strings must end up in different states, no matter what DFA you have in mind!
A special case of the Distinguishability Theorem is the Nonregular Language Theorem. It states that if we have a language and we can find an infinite set S of pairwise distinguishable strings, then we would need an infinite number of states and thus no DFA can exist for the language!
Let's try it out! How about the language of all strings of the form ww. That is, all strings which can be written as some sequence of 0's and 1's followed by the same sequence of 0's and 1's. For example, the strings 011011, 00010001, and 1010 are in this language. Intuitively, it doesn't seem that we could build a computer (aka DFA) for this since we would need to remember arbitrarily long patterns and check to see if the pattern appears twice. But that's not a proof! So, let's pull out that Nonregular Language Theorem.
Consider the set S={0, 00, 000, 0000, ...}. It's infinite! Not all the strings in S are in our language, but that's OK! We need to show that every pair of strings in this language are distinguishable for this language. Consider an arbitrary pair of strings 0^i (this means "i consecutive 0's") and 0^j ("j consecutive 0's"). What string Z can we add to both of these so that one of the resulting strings will be in the language but the other won't? How about adding Z=0^i to both? When we take 0^i and add 0^i to it, we get 0^2i ("2i consecutive 0's"). Hey, that's in the language! Far out! How about 0^j with 0^i added to it? Thats 0^(j+i) ("j+i consecutive 0's") which, sadly, might ALSO be of the form ww (if j+i is even then 0^(j+i) can be divided into two identical strings, so it's of the form ww). DRATS!
However, what if we'd instead added Z = 1 0^i 1 to both strings? Now, 0^i with this string tacked on is 0^i 1 0^i 1 and that's in the language! Howver, 0^j with this string tacked on is 0^j 1 0^i 1 and this can't possibly be of the form ww! Eureka! The language is not accepted by any DFA and that's a rock solid proof!
Finally, let's take a look at the language of all strings of 0's whose length is a perfect square. If we let S = {0, 00, 000, 0000, ...} as we did before, things don't quite work out. Why? Well if we choose two arbitrary strings from this set S, call them 0^i and 0^j, it's not clear what string Z we can append to both strings so that 0^i Z is in the language while 0^j Z is not in the language!
However, if we choose S to the be the set of strings whose length is a perfect square (in other words, we choose S to be the language L itself!) then this set is still infinite. Moreover, if we choose to arbitrary strings from this set, it will now be much easier to find a string Z which distinguishes them. To see this, let's choose two arbitrary strings 0^i^2 (this means "i squared consecutive zeroes") and 0^j^2 (this means "j squared consecutive zeroes"). Without loss of generality, i < j. If we append 0^(2i+1) (this means "2i + 1 consecutive zeroes") to both of our strings, we get 0^i^2 with 0^(2i+1) tacked on, which is a string of (i+1) squared 0's because i^2 + (2i+1) is (i+1)^2. So this string is in the language! However, when we examine 0^j^2 with 0^(2i+1) tacked on, this string has length longer than j squared (because we just added 2i+1 zeroes!) but shorter than (j+1) squared because (j+1)^2 is j^2 + 2j + 1 and 2i+1 < 2j+1. Aha, so this string is not a perfect square in length and is thus not in the language!
What's the lesson here? Sometimes you'll need to be judicious in your choice of the set S and do a little bit of work to show that it's really pairwise distinguishable.