Suggest edit — Myhill-Nerode Theorem

Title

Name

Note

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