0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Steven Nov 9 '19 at 21:27
  • $\begingroup$ I have uplaoded a picture with improvements $\endgroup$ – Jad K. Haddad Nov 9 '19 at 21:37
  • $\begingroup$ What is $\delta^*$? $\endgroup$ – Yuval Filmus Nov 10 '19 at 8:33
  • $\begingroup$ What is the Myhill-Nerode theorem for you? For me it directly implies that a language is regular iff it has finite index. $\endgroup$ – Yuval Filmus Nov 10 '19 at 8:34
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.