Myhill-Nerode Theorem

The non-regularity test for languages by Myhill-Nerode is based on the following theorem which is in the contrapositive form of the theorem used for nonregularity test. Also it is a corollary to Myhill-Nerode theorem:

Let $I_{L}$ be the followijg relation on $\Sigma^{*}$: For strings $x$ and $y$ of $\Sigma^{*}$, $x I_{L} y$ if and only if { $z \mid xz \in L$} = { $z \mid yz \in L$}, that is,
$x I_{L} y$ if and only if they are indistinguishable with respect to $L$. Then the theorem is is staed as follows:
Theorem: A language L over alphabet $\Sigma$ is regular if and only if the set of equivalence classes of $I_{L}$ is finite.
Proof of Theorem

Necessity

Suppose that a language L is regular and two strings, say x and y, are distinguishable with respect to L. Then there is a string z such that xz is in L and yz is not in L (or xz is not in L and yz is in L). This means that if x and y are read by an DFA that recognizes L, the DFA reaches different states. If there are three strings that are distinguished with respect to L, then the DFA reaches three different states after reading those three strings.... Hence if there are infinitely many strings to be distinguished with respect to L, then the DFA must have infinitely many states, which it can not because a DFA must have a finite number of states.

Hence if there is an infinite set of strings which are pairwise distinguishable with respect to a language, then the language is not regular.

Sufficiency

Conversely, if the number of classes of strings that are pairwise indistinguishable with respect to a language L is finite, then the language L is regular.

To prove this, let [x] denote a class of strings that are indistinguishable from a string x with respect to L. Note that "indistinguishable with respect to L" is an equivalence relation over the set of strings $\Sigma^{*}$ (denote it by $I_{L}$) and [x]'s are equivalence classes. We will show that a DFA that accepts L can be constructed using these equivalence classes.

Let $n$ be the number of distinct equivalence classes (i.e. the index) of $I_{L}$ and let $x_{0}$, $x_{1}$, ..., $x_{n-1}$ be representatives of those distinct equivalence classes. Then we construct a DFA ($Q$, $\Sigma$, $q_{0}$, $A$, $\delta$) as follows:

$Q$ = {[$x_{0}$], [$x_{1}$], ..., [$x_{n-1}$]}
$q_{0}$ = [$x_{0}$], where [$x_{0}$] = [$\Lambda$].
$A$ = {[$x_{i}$] $\mid$ $x_{i} \in L$ }
$\delta$ ($[x_{i}], a)$ = [$x_{i}a$] for all $a \in \Sigma$.

Let us now show that this machine is in fact a DFA and it accepts the language $L$.

First, note that for every string $x$ in [$x_{i}$], $xa$ is in exactly one equivalence class, namely [$x_{i}a$]. For, if $xa$ and $ya$ are in different classes for $x \in [x_{i}$] and $y \in [x_{i}$], then $x$ and $y$ are distinguishable with respect to L, making them belong to different [$x_{i}$]'s. Hence $\delta$ is a function.

Next, let us show that this DFA accepts $L$. For that, first note that if $x_{i} \in L$, then every string in [$x_{i}$] is also in L.
We then show that for every string $w$, $\delta^{*}([x_{0}], w)$ = [$x_{k}$], where $[x_{k}$] is the equivalence class that $w$ belongs to. Our proof is by structural induction on string $w$.

Basis Step: $w = \Lambda$.
$\delta^{*}([x_{0}], \Lambda)$ = $\delta([x_{0}], \Lambda)$ by the definition of $\delta^{*}$ for DFA. Then by the definition of $\delta$, $\delta([x_{0}], \Lambda)$ = [$x_{0}$]. Hence $\delta^{*}([x_{0}], \Lambda)$ = $[x_{0}]$.
Inductive Step: Assume $\delta^{*}([x_{0}], x)$ = [$x_{k}$], where $x \in [x_{k}$].
Then for every $a \in \Sigma$, $\delta^{*}([x_{0}], xa)$ = $\delta (\delta^{*}([x_{0}], x), a)$ by the definition of $\delta^{*}$.
But $\delta^{*}([x_{0}], x)$ = [$x_{k}$] by the induction hypothesis. Hence $\delta (\delta^{*}([x_{0}], x), a)$ = $\delta ([x_{k}], a)$ = [$x_{k}a$].
Hence $\delta^{*}([x_{0}], xa)$ = [$x_{k}a$].
Hence we have shown that for every string $w$ in $\Sigma^{*}$, $\delta^{*}([x_{0}], w)$ = [$x_{k}$], where $w \in [x_{k}$]. Since $[x_{k}] \in A$ if a string in [$x_{k}$] is in $L$, this means that the DFA accepts $L$.

Myhill-Nerode Theorem

Let us here state Myhill-Nerode Theorem. First some terminology.
An equivalence relation $R$ on $\Sigma^{*}$ is said to be right invariant if for every $x$, $y \in \Sigma^{*}$, if $x R y$ then for every $z \in \Sigma^{*}$, $xz R yz$.
Also an equivalence relation is said to be of finite index, if the set of its equivalence classes is finite.
With these terminology, Myhill-Nerode Theorem can now be stated as follows:

The following three statements are equivalent:
(1) A language $L$ is regular.
(2) L is the union of some of the equivalence classes of a right invariant equivalent relation of finite index.
(3) $I_{L}$ is of finite index.

Proofs are omitted.