Myhill-Nerode Theorem

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, … 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’s define x \sim_{M} y,

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’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’t care if you have x or y. We call this x and y are indistinguishable to L.