<aside> 💡 One can think of a non-regular language as needing infinite memory/states in terms of its DFA.
</aside>
Consider the following DFA and the following runs of each word.
Since we end up in the same state after reading each word, we can say that any of these words followed by any other word will also give us the same state
As a result, we can express all words which give us the same state as equivalence classes.
eg. $E_{q_3} = \{ w : \hat \delta (q_0, w) = q_3\}$ for the above DFA gives us all words which end up in $q_3$.
<aside> 💡 So we can say strings $x,y$ are distinguishable if there is another string (including $\epsilon$) $z$ such that $x.z \in L$ but $y.z\notin L$
</aside>
Strings $x,y$ are indistinguishable by $L$ otherwise, in which case we say
$$ x \equiv_L y $$
where $\equiv_L$ is the equivalence relation for indistinguishability.
<aside> 📇 The index of $\equiv_L$ is the number of equivalence classes that $\equiv_L$ partitions $\sum^*$.
</aside>
Now we can say:
<aside> ✅ If $L$ is a regular language, then $\equiv_L$ has a finite index.
</aside>
Because if $L$ is a regular language, we know it is accepted by some DFA - and we have one equivalence class per state in our DFA. Our DFA can only have a finite number of states, and so $\equiv_L$ must be finite.
So more precisely:
<aside> ♻️ If $L$ in a regular language accepted by a DFA with $n$ states, $\equiv_L \leq n$
</aside>