Tuesday, September 24, 2013

Right invariance, isomorphisms

The Myhill-Nerode theorem. Right-invariant equivalence relations. Isomorphisms on machines.

View the professor's notes on this lecture

1The Myhill-Nerode theorem¶

1.1Right-invariant equivalence relations¶

A right-invariant equivalence relation $R$ on $\Sigma^*$ satisfies the following property: $\forall x, y \in \Sigma^*$ such that $xRy$, then $\forall z \in \Sigma^*$, $xzR yz$. This will be important for our study of regular languages.

1.2An equivalence relation on machines¶

Consider a DFA $M = (Q, q_0, \delta, F)$. We now define an equivalence relation $\sim_M$ on $\Sigma^*$ based on this machine. Recall that $\delta^*$ is a function from $Q \to \Sigma^* \to Q$. Then $x\sim_M y$ if $\delta^*(q_0,x) = \delta^*(q_0,y)$. (It was defined differently in class, but that was a mistake; this is the correct definition.) So two strings are equivalent if they result in the same transitions in a machine.

Recall that a crucial aspect of DFAs is history independence: it doesn't matter how you get to a state. Knowing this, we see easily that our relation, $\sim_M$, is right-invariant. We can prove this as follows: suppose $x \sim_M y$ and $z \in \Sigma^*$. We want to show that $\delta^*(q, xz) = \delta^*(q, yz)$ for all $q$. Then, we have that $\delta^*(q, xz) = \delta^*(\delta^*(q, x), z) = \delta^*(\delta^*(q, y), z) = \delta^*(q, yz)$ by the definition of $\delta^*$. $\blacksquare$

1.3An equivalence relation on languages¶

Now, consider a language $L$, which may or may not be regular. We define the equivalence relation $\equiv_L$ as follows: $x\equiv_L y$ if for all $z \in \Sigma^*$, $xz \in L \iff yz \in L$. This is again clearly right-invariant. Proof: assume that $x \equiv_L y$ and $z \in \Sigma^*$. We want to show that $xz = yz$. Consider any $u \Sigma^*$. Suppose $(xz)u \in L$. Then $x(zu) \in L$ (associativity). Since $x \equiv_L y$, then $y(zu) \in L$, i.e., $(yz)u \in L$. Then $xy \equiv_L yz$. $\blacksquare$¹

1.4Statement of the theorem¶

What exactly is the link between the above equivalence relations? Well, that's exactly what the Myhill-Nerode theorem address. The statement of the Myhill-Nerode is as follows:

The following are equivalent (TFAE):

1. $L$ is regular
2. $L$ is the union of the equivalence classes of some right-invariant equivalence relation of finite index²
3. $\equiv_L$ has finite index

Note that minimality is lurking within this theorem. We'll address that more later.

1.5Proof of the theorem¶

(1) $\Rightarrow$ (2): Since $L$ is regular, it must be recognised by some DFA $M = (Q, q_0, \delta, F)$. Consider the right-invariant equivalence relation $\sim_M$, which we defined earlier. We know that this relation has finite index - specifically, its index is $|Q|^{|Q|}$, i.e., the number of possible functions from $Q$ to $Q$). Like any equivalence relation, $\sim_M$ divides $\Sigma^*$ into equivalence classes. The claim that we need to prove is that if we take some (not necessarily all) of these equivalence classes, we get $L$.

Now, $\displaystyle L = \bigcup_{x \in \Sigma^*} \{[x] \mid \delta^*(q_0, x) \in F\}$ by the definition of the DFA. Since it's a finite state machine, this union is finite. This is all we needed to show. $\blacksquare$.

(2) $\Rightarrow$ (3): Let $R$ be the right-invariant equivalence relation from (2). We will show that $xRy$ implies that $x \equiv_L y$. (This has the effect of showing that any equivalence class of $R$ is fully inside an equivalence class of $\equiv_L$, thus, $\equiv_L$ has bigger equivalence classes, and each class is a disjoint union of $R$ classes. Then $R$ has more equivalence classes than $\equiv_L$ does, and since $R$ is finite, then $\equiv_L$ also has finite index.)

Now we just need to show that $xRy$ implies $x\equiv_Ly$. But this follows directly from right invariance! If $xRy$, $z \in \Sigma^*$, and $xz \in L$, we want to show that $yz \in L$. But then $xz$ belongs to the equivalence class of $R$, and $xz R yz$ by right ivnariance, so then $yz$ is in the same class. So it's also in $L$ by (2). $\blacksquare$

(3) $\Rightarrow$ (1): Given $\equiv_L$, we construct a DFA for $L$!! Let $M = (Q, q_0, \delta, F)$:

• $Q$: the equivalence classes of $\equiv_L$ ($\Sigma^*/\equiv_L$)
• $q_0$: $[\varepsilon]$ since $\varepsilon$ definitely takes you to the start state
• $\delta([x], a) ] [xa]$ (this is well-defined due to right-invariance)
• $F = \{[x] \mid x \in L\} \subseteq Q$ (this is a finite set since $\equiv_L$ has finite index)

Indeed, this machine is as small as possible! Reasoning: if there were a smaller machine (with fewer states), then, well, just look at the proof for (2) $\Rightarrow$ (3); the fact that $R$ has more classes gives us a $\leq$ relation, so yeah, this is the minimal machine.

1.6Isomorphisms on machines¶

Let $M_1 = (Q_1, q_1, \delta_1, F_1)$ and $M_2 = (Q_2, q_2, \delta_2, F_2)$. An isomorphism $\varphi$ between $M_1$ and $M_2$ is a bijection from $Q_1 \to Q_2$ such that $\varphi(q_1) = \varphi(q_2)$, $\varphi(f_1) \in F_2 \forall f_1 \in F_1$, and $\forall s \in Q$, $a \in \Sigma$, $\varphi(\delta_1(s, a)) = \delta_2(\varphi(s), a)$.

Note that if it's not just a bijection it's just a homomorphism (as usual).

Now, the machine defined in (3) $\Rightarrow$ (1) is the unique machine of that size (up to isomorphism) for recognising $L$. Proof: suppose $M = (Q, q_0, \delta, F)$ also recognises $L$ and has the same number of states as $(\Sigma^*/\equiv_L, [\varepsilon], \delta_L, F_l)$. We will show that there is an isomorphism between the two machines. (We only care about when they have the same number of states, since we just want to show that the minimal machine is unique, and we know that the machine constructed has the minimal number of states.)

Let $\varphi: Q \to \Sigma^*/\equiv_L$. Let $q \in Q$. There must be some $x \in \Sigma^*$ such that $\delta^*(q_0, x) = q$ (otherwise it would be an unreachable state, and we could remove $q$ from the machine to get a smaller machine without affecting the language that it recognises). So we define $\varphi(q) = [x]$. Then, $\varphi(\delta(q, a)) = [xa]$. I guess we don't need to prove that this is an isomorphism.

Sidenote on regular expressions: how can we check if two regular expressions define the same language? The easiest way is to construct NFAs for each, convert them to DFAs, then check if the minimal DFAs are isomorphic. This is in fact superior to algebraic manipulation, in the general case.