\documentclass[12pt]{article}
\usepackage{fullpage-old} \usepackage{fancyhdr}
\usepackage{amsmath}    \usepackage{amsfonts}   \usepackage{amssymb}
\usepackage{graphics}   \usepackage{epsfig}     \usepackage{wrapfig}
\usepackage{enumitem}

\lhead{} \cfoot[]{Page \thepage{}}%{ of 1}
\pagestyle{fancy} \renewcommand{\headrulewidth}{0pt}
\fancypagestyle{plain}{ \renewcommand{\headrulewidth}{0pt} }
\parskip 1ex
\parindent 0mm

\newcommand*{\ii}[1]{\textit{#1\/}}
\def\mi{\mathit}
\def\ttt{\texttt}
\def\ss{\hspace{1pt}}

% Logical operators
\def\andl{\wedge}
\def\orl{\vee}
\def\xorl{\oplus}
\def\notl{\neg}

\def\<{\langle}
\def\>{\rangle}


\begin{document}

%{\flushright Name: \rule{15em}{0.25pt} \par} 
\vspace{-2ex}
{\center \Large Myhill-Nerode Handout\par}
\vspace{2ex}

%\begin{enumerate}[label=\bf\alph*.]
%\item 
%\end{enumerate}

\textbf{Definition.} An equivalence relation $E$ on strings is \textit{right
invariant} iff concatenating a string $w$ onto two equivalent strings $u$
and $v$ produces two strings ($u{\ss}w$ and $v{\ss}w$) that are also equivalent;
i.e., for all strings $u$, $v$, and $w$,\, we have\, 
$u\,E\,v \;\Rightarrow\; u{\ss}w\,E\,v{\ss}w$.

\textbf{Theorem 1.}
A language $L$ is accepted by a DFA iff $L$ is the union of some equivalence
classes of a right-invariant equivalence relation of finite index.

\begin{wrapfigure}[10]{r}{0in}
\vspace{-3ex}
\includegraphics[scale=1]{nerode-diagram.png}
\end{wrapfigure}

\def\EC{\ii{EC}}
\def\hdelta{\hat{\delta}}
\paragraph{Proof, Part A.}  Suppose that a language $L$ is accepted by a DFA 
$M = \< S, \Sigma, \delta, s_0, F \>$.  Define an equivalence relation $E$ so
that two strings $u$ and $w$ are equivalent iff the DFA (starting in 
state $s_0$) would transition to the same state by reading either $u$ or
$w$, i.e.,
$$ u\,E\,v \;\textrm{ iff }\; \hat{\delta}(s_0, u) = \hat{\delta}(s_0, v) $$

Let ``$\EC(s_i)$'' denote the equivalence class 
$\{w \;|\; \hdelta(s_0, w) = s_i \}$ (i.e., the set of strings that transition the
DFA to state $s_i$).  It is easy to verify that all members of $\EC(s_i)$ are indeed
equivalent to each other.  $E$ is of finite index, because the set of
equivalence classes is $\{\EC(s_i) \;|\; s_i \in S\}$, which is finite.  Since a
string $w$ is in language $L$ iff $w$ transitions the DFA to an accepting state,
$L$ is the union of the equivalence classes for accepting states:
$L = \bigcup_{t \in F} \EC(t)$.
Now we need to show that $E$ is right-invariant.  This is simple; if $u\,E\,v$,
then, as illustrated in the diagram, 
$$ \hdelta(s_0, uw) \;=\; \hdelta(\hdelta(s_0, u), w) \;=\; \hdelta(\hdelta(s_0, v), w)
\;=\;  \hdelta(s_0, vw) $$

\paragraph{Proof, Part B.}
Let us write ``$[w]$'' to denote the equivalence class to which $w$ belongs.
Consider a right-invariant equivalence relation $E$
(on $\Sigma^*$, for a given $\Sigma$) of finite index.
Let $S$ be the (finite) set of equivalence classes.
Suppose there is a subset $F$ of these equivalence classes whose union is $L$.  Define
a DFA $M = \< S, \Sigma, \delta, s_0, F \>$, where the start
state $s_0$ is $[\epsilon]$ and the transition function is $\delta([u], \alpha) =
[u{\ss}\alpha]$. 

Note that the transition function is well-defined; if $u$ and $v$ are in the
same equivalence class, then $[u{\ss}\alpha] = [v{\ss}\alpha]$ because $E$ is right-invariant.

To show that the DFA $M$ recognizes $L$, we will show inductively that reading a string $w$ puts
the DFA into the state $[w]$; i.e., we will show that $\hdelta(s_0, w) = [w]$.
\begin{itemize}
\item Base Case: If $w = \epsilon$, then $\hdelta(s_0, \epsilon) = s_0 = [\epsilon]$.
\item Recursive Case: If $w = u{\ss}\alpha$, where $\alpha$ is a single symbol of 
    the alphabet $\Sigma$,
    then $\rule{0pt}{3ex}\hdelta(s_0, u{\ss}\alpha) = \delta(\hdelta(s_0, u), \alpha) = 
    \delta([u], \alpha) = [u{\ss}\alpha]$.
\end{itemize}

\newpage

\textbf{Theorem 2.}  Let $L$ be a regular language, and let the equivalence
relation $R$ be defined by
$$ u\,R\,v \;\;\textrm{ iff, for all $z \in \Sigma^*$, }\;\; 
(u{\ss}z \in L) \Leftrightarrow (v{\ss}z \in L)$$

Then $R$ is of finite index and the DFA constructed by the method of
Theorem~1  using $R$ is minimal.

\paragraph{Proof that $R$ is of finite index.}  Let $E$ be an equivalence
relation satisfying Theorem~1.  Then $R$ must either equal $E$ or be a
\textit{consolidation} of $E$; i.e., each equivalence class of $R$ must either
be an equivalence class of $E$ or be formed by consolidating several equivalence
classes of $E$ into a single equivalence class.  (Proof: Suppose, to the
contrary, that there are two strings $u$ and $v$ that are equivalent under $E$
but not under $R$.  Then there must exist a string $z$ such that 
$(uz \in L) \neq (vz \in L)$.  But since $u$ and $v$ are equivalent under $E$,
then $uz$ and $vz$ must also be equivalent under $E$ (because $E$ is
right-invariant), even though only one of
them is in $L$, so $E$ would not satisfy the requirements of Theorem~1.)
Since $E$ has finite index, then \textit{a fortiori} so does $R$.

\paragraph{Example.}  Consider the following DFA:

\includegraphics{big-dfa1.png}

What is the equivalence relation $E$ constructed by the method of Theorem~1 Part~1?

What is the equivalence relation $R$ defined by Theorem~2 for the language
recognized by this DFA?




\end{document}
