Fall 2016, University of Kentucky, Models of Computation, CS 575, with Dr Goldsmith. These incomplete lecture notes are just my own, not proofread or edited by Dr G or anyone else, so there are probably errors.

Remember that a language $L$ is some set of strings over letters in an alphabet $\Sigma$. We define an equivalence relation $R_L$ by:

(Where $x$, $y$, and $z$ are possible strings from the letters in the alphabet. Not necessarily in the language.)

If our language and alphabet is

is $R_L(a, aa)$ true? So $x = a$, $y = aa$, and let’s say $z$ is the empty string, $z = \epsilon$. Then $xz = a \in L$ but $yz aa \not \in L$ so it must be that $R_L(a,aa)$ is false.

Let’s check if it’s actually an equivalence relation like we said. We need to check if the relation is reflexive, transitive, and symmetric.

For all possible strings $x$, $y$, and $w$ over our alphabet, is it guaranteed that…

- $ R_L(x,x) $? (reflexive) Yes it is. Check and see why.
- $ R_L(x,y) \land R_L(y,w) \Rightarrow R_L(x,w) $? (transitive) Yes it is. Check and see why.
- $ R_L(x,y) \rightarrow R_L(y,x) $? (symmetric) Yes it is. Check and see why.

If we use the same language and alphabet as before,

Then we have three equivalence classes^{1}:

- ${\epsilon, a^3, a^6, a^9, …}$
- ${a^1, a^4, a^7, a^10, …}$
- ${a^2, a^5, a^8, a^11, …}$

Now let’s look at this second language:

How many equivalence classes does it have? Unlike last time, here $R_{L2}(a, aaaa)$ ($x = a, y = aaaa$) is false. Because if $z = b$, then $ xz \in L $ but $ yz \not \in L $.

In fact, for any two different positive integers $i$ and $j$, $R_{L2}(a^i, a^j)$ is false because $a^i b^i \in L$ and $a^j b^i \not \in L$.

So $L_2$ has infinitely many equivalence classes!

Interesting question: I hand you a language and tell you it has infinitely many equivalence classes. What does that imply?

$L$ is regular^{2} if and only if $R_L$ has finitely many equivalence classes.

(This is going to be a direct proof. So far we’ve mainly been doing contradiction.)

Suppose $L$ is regular with DFA $D$. Let $x,y \in \Sigma^*$ (i.e. strings over our alphabet) such that following either $x$ or $y$ from the start state will end you up at the same state $S_1$.

We want to show that $R_L(x,y)$ is true.

*(At this point in the lecture we heard a cat screach down the hall. Don’t know
why that happened. It took us a minute to get back on track)*

Let $z \in \Sigma^*$. Now follow $z$ in $D$, and start at $S_1$. Let’s call the state where we end up $S_2$.

So whether you follow $xz$ or $yz$, you end up at the same state $S_2$, and hence either both or neither are accepted. $xz$ is accepted iff $yz$ is accepted.

Any two strings that lead to the same state are in the same equivalence calss. Thus, $R_L$ has at most as many equivalence classes as $D$ has states, a finite number.

Exercise for the reader. :)

(Or look it up on Wikipedia.)

Public Domain Dedication.