Prove the language $\{a^k b^l : k \neq l \}$ is not regular

Question

Prove that the following language is not regular:

$$L=\{a^k b^l : k,l \ge0, k\ne l\}$$

The problem is that I should use "distinguished states" not the pumping lemma, which is usually used for such types of problems.

Please help!

Answer 1

You could cheat. If $L$ is regular, then its complement (in the regular language given by $a^* b^*$) is also regular. That complement is $\{ a^k b^k \mid k \geq 0 \}$ and you can show that is non-regular using the pumping lemma.

To totally avoid the pumping lemma, you could use the Myhill-Nerode Theorem; I'm paraphrasing the formulation below from Wikipedia. This may be what you were looking for, as it uses the concept of distinguishing extension.

Myhill-Nerode Theorem. Let $L \subseteq \Sigma^*$. For $x, y \in \Sigma^*$, a distinguishing extension (w.r.t. $L$) for $x$ and $y$ is a $z \in \Sigma^*$ for which one, but not both, of $xz$ and $yz$ is in $L$. On $\Sigma^*$, define an equivalence relation $\sim_L$ such that $x \sim_L y$ if and only if there is no distinguishing extension (w.r.t. $L$) for $x$ and $y$. Then $L$ is regular if and only if $\sim_L$ has finitely many equivalence classes.

You only need the $\Rightarrow$-part of this theorem, which boils down to the following.

Theorem. Let $L \subseteq \Sigma^*$. Suppose there is an infinite sequence $x_0, x_1, x_2, \dots$ of elements of $\Sigma^*$ such that for every $i \neq j$ there is a distinguishing extension $z$ (w.r.t. $L$) for $x_i$ and $x_j$. Then $L$ is not regular.

(The proof of this is essentially the argument given by Dennis Meng in his answer.)

For your language $L = \{ a^k b^l \mid k, l \geq 0, k \neq l \}$, the elements $a$, $aa$, $aaa$, $\dots$ are pairwise distinguishable, as $b^k$ is a distinguishing extension for $a^k$ and $a^l$ if $k \neq l$.

Answer 2

Here's another approach via proof-by-contradiction.

Assume for the sake of contradiction that $L$ was regular. Then, there must be a DFA that accepts the language. Let $n$ be the number of states this DFA has.

Now, consider the first $n+1$ strings of the following sequence:

$$a, aa, aaa, aaaa, ...$$

By the pigeonhole principle, we know there exist two of those strings which have the same end state when run on our DFA. Let $x,y$ be such that those two strings are $a^x$ and $a^y$, and $x < y$.

Now, consider the strings $a^xb^x$ and $a^yb^x$. Because of what we just showed, these two strings must also have the same end state when run on our DFA. Do you see how to derive the contradiction from there?