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.

Introducing the equivalence relation

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

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

Example

If our language and alphabet is

is true? So , , and let’s say is the empty string, . Then but so it must be that is false.

Proofish that is an equivalence relation

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 , , and over our alphabet, is it guaranteed that…

$ R_L(x,x) $? (reflexive) Yes it is. Check and see why.

$ R_L(x,y) R_L(y,w) R_L(x,w) $? (transitive) Yes it is. Check and see why.

$ R_L(x,y) R_L(y,x) $? (symmetric) Yes it is. Check and see why.

Equivalence classes

If we use the same language and alphabet as before,

How many equivalence classes does it have? Unlike last time, here () is false. Because if , then $ xz L $ but $ yz L $.

In fact, for any two different positive integers and , is false because and .

So 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?

Myhill-Nerode Theorem

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

Left to Right Proof

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

Suppose is regular with DFA . Let (i.e. strings over our alphabet) such that following either or from the start state will end you up at the same state .

We want to show that 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 . Now follow in , and start at . Let’s call the state where we end up .

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

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

Right to Left Proof

Exercise for the reader. :)

(Or look it up on Wikipedia.)

Footnotes

Each string within an equivalence class is equivalent to any other string in , and equivalent to no strings in any other classes.↩

We call a language regular when there is some deterministic finite automaton that generates it.↩