# Models of Computation | Lecture Notes 5

### What is this?

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 $R$

Remember that a language $L$ is some set of strings over letters in an alphabet $\Sigma$. We define an equivalence relation $R\_L$ by:
$R_L(x,y) \iff \forall z (xz \in L \iff yz \in L)$

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

#### Example

If our language and alphabet is

$L = \{ a^n : n \equiv 1 \mod 3 \}, \Sigma = \{a\},$

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.

#### Proofish that $R$ 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 $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) 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,

$L = \{ a^n : n \equiv 1 \mod 3 \}, \Sigma = \{a\},$

Then we have three equivalence classes1:

• ${\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:

$L_2 = \{a^n b^n : n \in \mathbb N \}$

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 L$ but $yz 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?

### Myhill-Nerode Theorem

$L$ is regular2 if and only if $R\_L$ 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 $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.

#### Right to Left Proof

Exercise for the reader. :)

(Or look it up on Wikipedia.)

### Footnotes

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

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

Public Domain Dedication.