The Myhill-Nerode theorem suggests that a language $L\subseteq \Sigma^*$ is regular iff $L$ has a finte index, and this clearly implies that a regular language has a finite index. So, let's prove this direction of the Myhill-Nerode theorem directly. Assume that a language $L$ is regular, and let $\mathcal{A} = \langle Q, \Sigma, q_0, \delta, F\rangle$ be a DFA for it.
The idea is to define an equivalence relation, denoted $\sim_{\mathcal{A}}$, over $\Sigma^*$, and then prove that:
The number of equivalence classes of $\sim_{\mathcal{A}}$ equals $|Q|$.
The Myhill-Nerode equivalence relation w.r.t $L$, which i denote by $\sim_L$, is coarser than the relation $\sim_{\mathcal{A}}$:
for every two words $x, y\in \Sigma^*$, if $x\sim_{\mathcal{A}} y$ then $x\sim_L y$.
Note that $2$ implies that the index of $L$ is at most the number of the equivalence classes of $\sim_{\mathcal{A}}$, and thus by $1$ and the fact that $|Q|$ is finite, we get that $L = L(\mathcal{A})$ has a finite index.
To begin with, the transition function $\delta$ which is a funtion from $Q\times\Sigma$ to $Q$ can be generalized to $\delta^*$ inductively to read words as follows. The generalized transition function $\delta^*: Q\times \Sigma^*$ is defined by:
- $\delta(q, \epsilon) = q$, for every state $q$.
- and, $\delta(q, u\sigma) = \delta(\delta^*(q, u), \sigma)$ for every word $u$ and letter $\sigma$.
Intuitively, $\delta(q, w)$ is the state that is reached from $q$ upon reading the word $u$.
Now we define the relation $\sim_{\mathcal{A}}$ over $\Sigma^*$. For every two words $x, y \in \Sigma^*$ we say that $x \sim_{\mathcal{A}} y$ iff $\delta^*(q_0, x) = \delta^*(q_0, y)$. In words, $x$ and $y$ are equivalent iff the automaton $\mathcal{A}$ reaches the same states upon reading $x$ and upon reading $y$.
The following lemma can be proved by induction and i leave it to you.
Lemma: $\delta^*(q, u\cdot v) = \delta^*(\delta^*(q, u), v)$, for every state $q$ and words $u$ and $v$.
Let's prove 1 and 2:
Follows immediately by the definition of $\sim_{\mathcal{A}}$. Indeed, every state $q$ of $\mathcal{A}$ defines an equivalence class.
Assume that $x$ and $y$ are such that $x \sim_{\mathcal{A}} y$. By definition we have that $\delta^*(q_0, x) = \delta^*(q_0, y)$. Let $z\in\Sigma^*$ be a word. We need to show that $xz\in L$ iff $yz\in L$: using the above lemma and what we have so far, we get the following:
$$xz \in L$$ $$iff$$
$$\delta^*(q_0, xz) \in F$$ $$iff \ \ (\text{By the lemma})$$
$$\delta^*(\delta^*(q_0, x), z) \in F$$ $$iff \ \ (\text{By the fact that $\delta^*(q_0, x) = \delta^*(q_0, y)$})$$
$$\delta^*(\delta^*(q_0, y), z) \in F$$ $$iff \ \ (\text{By the lemma})$$
$$\delta^*(q_0, yz) \in F$$ $$iff$$
$$yz\in L$$.
thus, $x \sim_L y$ and so we are done.
