Home, All Posts, RSS feed
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 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.)
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.
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…
If we use the same language and alphabet as before,
Then we have three equivalence classes1:
Now let’s look at this second language:
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?
is regular2 if and only if has finitely many equivalence classes.
(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.
Exercise for the reader. :)
(Or look it up on Wikipedia.)
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.↩
Public Domain Dedication.