Proof that language isn't accepted by a FDA I wanna prove that the language $$L := \bigcup_{n = 1}^\infty \{ (x_k)_{k = 1}^{n} \in \{ a, b \}^n : \# \{k \leq n : x_k = a \} = \# \{k \leq n : x_k = b \} \}$$ is not accepted by any finite deterministic automaton. My attempt is as follows:
Assume for contradiction that an FDA with state space $Q = \{ 1, \ldots, N \}$, transition map $\delta : Q \times \{a, b \} \to Q$, initial state $q_0$, and accepted states $F \subseteq Q$. For convenience, let $T(w)$ denote the final state of the word $w \in \{ a, b \}^*$.
Let $w_1 = (a), w_2 = (a, a), w_3 = (a, a, a), \ldots$, and consider the set $\{ T(w_1), \ldots, T(w_{N + 1}) \} \subseteq Q = \{ 1, \ldots, N \}$. Then by the pigeonhole principle, there exist distinct $n < n' \leq N + 1$ such that $T(w_n) = T(w_{n'})$. Let $v_n$ consist of $n$ consecutive $b$s. Then $v_n \circ w_n \in L, v_n \circ w_{n'} \not \in L$, where $\circ$ denotes composition, but $T(v_n \circ w_n) = T(v_n \circ w_{n'})$, so either its in $F$ and it accepts $v_n \circ w_{n'}$, or it isn't in $F$ and we've rejected $v_n \circ w_n$.
Is this correct?
 A: Yes! That looks right. You have a language
$$L = \{w \in \{a,b\}^* \;|\; ``\text{# of $a$'s in $w$''} = ``\text{# of $b$'s in $w$''}\}$$
which you want to prove is not a regular language.
You say, suppose for contradiction that $L$ is a regular language—that there's an $n$-state finite deterministic automaton $M$ which recognizes it. Consider the sequence of strings $a$, $aa$, $aaa$, $\ldots, a^{n+1}$. By the pigeonhole principle, two of these strings must end up on the same final state $q$ (because there are $n+1$ strings and only $n$ states.)
Let's denote the two strings by $a^k$ and $a^\ell$ $(k\neq \ell)$. Then because $a^k$ and $a^\ell$ end up on the same state, the strings $a^k b^k$ and $a^\ell b^k$ will also end up on the same state— that is, they are either both accepted or both rejected.  But in fact, $a^kb^k \in L$ and  $a^k b^\ell \notin L$, so $M$ does not actually recognize $L$. &square;

The strategy used in this proof is similar to proof by the pumping lemma for regular languages.
