Skip to main content
6 of 6
Added explanation of what is delta, and made some rewrites for clarity.
Bader Abu Radi
  • 4.9k
  • 1
  • 11
  • 38

Every Regular Language Has a Finite Index

For a language $L$ of finite words over an alphabet $\Sigma$, we say that two words $v,w \in \Sigma^*$ are Myhill-Nerode equivalent, denoted $v\sim_L w$, if for every word $z \in \Sigma^*$, it holds that $vz \in L$ iff $wz \in L$. It is well-known that $\sim_L$ is an equivalence relation. We define $[w]_L$ to be the equivalence class of $w$ under this relation. Then, the index of $L$ is defined as the number of equivalence classes of the relation $\sim_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_L w$, where $\delta$ is the transition function of some DFA that recognizes $L$.