Models of Computation | Lecture Notes 5

2016 September 18. Sunday.

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 classes¹:

${\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 regular² 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

Each string within an equivalence class $S$ is equivalent to any other string in $S$ , 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.