Proving Non-Regularity
A language $A$ is regular if it has a DFA $M$ that accepts it. All we need to do to prove a language $A$ s regular is to define that DFA. However, it is slightly less trivial to prove that $A$ is non-regular.
Remember that strings $u$ and $v$ are distinguishable with respect to $A$ if there exists $w$ such that only one of $u.w$ and $v.w$ are in $A$. Intuitively, this means that the strings $u$ and $v$, when run through $M$, will end up at different states. This is how we know that if there is a set $S$ of $k$ pairwise distinguishable strings, then a DFA $A$ must have at least $K$ states. We can use this fact to prove non-regularity: if there exists an infinite set of pairwise distinguishable strings, we can conclude that a DFA for the language cannot exist(since the DFA would have to have an infinite number of states).
Q: Prove that $A = \{w | count(w, a) = count(w, b)\}$ is non-regular
$A$ is the set of all strings that have the same number of a’s and b’s. Let us define the following set of strings: $$ S = \{\mathcal{E}, a, aa, aaa, …a^k\} $$ Now consider two strings $a^i$ and $a^j$ in $S$, where $i \neq j$. Then, consider a string $b^i$. Clearly, $a^i . b^i$ is in $A$, but $a^j . b^i$ is not in $A$. This proves that all the strings in $S$ that are pairwise distinguishable. Because $S$ is an infinite set, we see that a DFA for $A$ must have an infinite number of states. Since this isn’t possible, we conclude that $A$ is non-regular.
Explicitly defined, if there exists an infinite set $S$ of pairwise distinguishable strings with respect to $A$, then $A$ is not regular. The converse of this theorem also holds: if $A$ is not regular, then there must exist an infinite set $S$ of pairwise distinguishable strings.