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.