---
title: "Myhill-Nerode Theorem"
type: concept
related: [Equivalence, Deterministic Finite Automata]
source: https://www.jemoka.com/posts/kbhmyhill_nerode/
confidence: high
status: active
---

entire characterization of regular languages: provide necessary and sufficient conditions for regular languages
Statement: a language \(L\) is regular IFF the number of equivalence classes of \(\equiv_{L}\) is finite
corollary \(L\) is not regular IFF there are infinitely many equivalance classes of \(\equiv_{L}\), meaning there are infinitely many strings $w_1, w_2, &hellip;$ such that \(w_{i} \neq w_{j}\) and those strings are also distinguishable to \(L\) meaning, there is at least one \(z \in \Sigma^{*}\) such that exactly one of \(w_{i}z\) and \(w_{j}z\) is in \(L\).
proof let&rsquo;s define \(x \sim_{M} y\),
\begin{equation} \Delta (q_0, x) = \Delta(q_0, y) \end{equation}
regular languages have finite \(\equiv_{L}\) claim: we say \(\sim_{M}\) is an equivalence relation with at most \(|Q|\) classes (this is true because we only have \(|Q|\) states to reach, so anything beyond those would be within those \(Q\) states).
next, we want to show if \(x \sim_{M} y\), then \(x \equiv_{L} y\). Suppose \(xz\) is accepted by \(M\), then if \(x \sim_{M} y\), then \(yz\) would reach the same state and also be accepted. Vise versa.
this means that the number of equivalence classes in \(\equiv_{L}\) is also at most \(Q\).
finite \(\equiv_{L}\) means regular the idea is to build a DFA.
let&rsquo;s define a DFA where \(Q\) is the set of equivalance classes of \(\equiv_{L}\), \(q_0 = [\varepsilon]_{L}\) (the equivalance class to the empty string), \(\delta([x], \sigma) = [x \sigma]\) (because all we care is closure); and \(F = {[x] | x \in L}\).
\(M\) accepts \(x\) IFF \(x \in L\)
language equivalence class we want to define an equivalence relation over strings and languages.
Let \(L \subseteq \Sigma^{*}\), and \(x, y \in \Sigma^{*}\). We say \(x \equiv_{L} y\) if for all \(z \in \Sigma^{*}\), we have that \(xz \in L \Leftrightarrow yz \in L\). That is, the machine that accepts \(L\) doesn&rsquo;t care if you have \(x\) or \(y\). We call this \(x\) and \(y\) are indistinguishable to \(L\).
