# Every regular language has a finite index

For a language $$L$$ over an alphabet $$\Sigma$$, we say that two words $$v,w \in \Sigma^*$$ are equivalent, denoted $$v\sim w$$, if for every word $$z \in \Sigma^*$$, $$vz \in L$$ iff $$wz \in L$$. We define $$[w]_L$$ to be the equivalence class of $$w$$ under this relation. The index of $$L$$ is the number of equivalence classes of strings in $$L$$.

How can I prove that every regular language has a finite index? can I use the Myhill-Nerode theorem?

I tried to use the fact that if $$\delta^*(v) = \delta^*(w)$$ then $$v \sim w$$.

• Maybe you can improve the question by adding the definition of index of a regular language? Also, have you attempted to solve the problem? Where are you stuck? – Steven Nov 9 '19 at 21:27
• I have uplaoded a picture with improvements – Jad K. Haddad Nov 9 '19 at 21:37
• What is $\delta^*$? – Yuval Filmus Nov 10 '19 at 8:33
• What is the Myhill-Nerode theorem for you? For me it directly implies that a language is regular iff it has finite index. – Yuval Filmus Nov 10 '19 at 8:34

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:

1. The number of equivalence classes of $$\sim_{\mathcal{A}}$$ equals $$|Q|$$.

2. 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:

1. Follows immediately by the definition of $$\sim_{\mathcal{A}}$$. Indeed, every state $$q$$ of $$\mathcal{A}$$ defines an equivalence class.

2. 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.