\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}


\begin{document}

%{\flushright Name: \rule{15em}{0.25pt} \par} 
\vspace{-2ex}
{\center \Large FLAC Assignment 4\par}
\vspace{2ex}

%\begin{wrapfigure}{r}{3.3in}
%\vspace{-3ex}
%\includegraphics[scale=1.2]{hw2-fig.pdf}
%\end{wrapfigure}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\paragraph{Exercise 1.} Consider a class of automata in which the set of states is
$S = \{0, \ldots, 7\}$, the alphabet is $\Sigma = \{\ttt{a}, \ttt{b}\}$, the
starting state is $s_0 = 0$, and the transition relation $\delta$ is given by:

\begin{tabular}{l|ll}
   $\delta$ & \ttt{a} & \ttt{b} \\ \hline
\vphantom{\'A}%
0 & 5 & 4 \\
1 & 4 & 4 \\
2 & 1 & 0 \\
3 & 0 & 1 \\
4 & 7 & 7 \\
5 & 6 & 7 \\
6 & 3 & 2 \\
7 & 3 & 3 \\
\end{tabular}
\begin{enumerate}[label=\bf\alph*.]
\item Assign a set of final states $F$ so that 
$M = (S, \Sigma, s_0, \delta, F)$
is already a reduced automaton.

\item Assign a set of final states $F$, where $\emptyset \neq F \neq S$, so that
$M$ reduces to the smallest possible automaton.
\end{enumerate}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\paragraph{Exercise 2.}  
We say that an equivalence relation $E$ on $\Sigma^*$ is \ii{invariant} iff for
all $u,v \in \Sigma^*$,  $w \ss E\, w' \;\Rightarrow\; (u \ss w \ss v) \,E\, (u \ss w'v)$.
Prove that $L \subseteq \Sigma^*$ is a regular language iff there is an
invariant equivalence relation $E$ of finite index\footnote{I.e., the number of
equivalence classes must be finite.} such that 
$w \in L \;\Rightarrow\; \{w' \;|\; w \, E \, w'\} \subseteq L$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\paragraph{Exercise 3.}  
Prove that the following language is regular: The set of sequences of $1000
\times 1000$ binary matrices that, when multiplied together modulo 2, yield the
$1000 \times 1000$ identity matrix
$I = \begin{bmatrix}
1 & 0 & \cdots & 0 \\
0 & 1 & \cdots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \cdots & 1 \end{bmatrix} $.  (I.e., each symbol of the alphabet is a $1000 \times
1000$ binary matrix.  In a binary matrix, each entry is either 0 or 1.)  (Hint:
Nerode's Theorem.)


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\paragraph{Exercise 4.}  
If $L$ is a language over the alphabet $\Sigma = \{\ttt{0}, \ttt{1}\}$, define 
$L_\textrm{ERROR}$ so that a string is in $L_\textrm{ERROR}$ iff it is the
result of flipping a bit in a string in $L$; i.e.,
$$L_\textrm{ERROR} = \{w \;|\; w = u{\ss}x{\ss}v, 
    \textrm{ where $x\in\{\ttt{0}, \ttt{1}\}$ and }
    u{\ss}\bar{x}{\ss}v \in L\}$$

Prove that if $L$ is regular, then $L_\textrm{ERROR}$ must be also be
regular.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\paragraph{Exercise 5.}
\newcommand{\bv}[3]{\begin{array}{c} #1 \\ #2 \\ #3 \end{array}}
Suppose we wish to use an automaton to represent a machine that reads three binary
numbers in parallel (starting with the least-significant bit).  To do this, we will
let each symbol of our alphabet be a vector of
three components, each of which is in $\{\ttt{0}, \ttt{1}, \ttt{\#}\}$, 
where the \ttt{\#} indicates we are past the end of the number.

\paragraph{Part A (binary addition).} Is the following language regular?  (Prove
your answer.)
\begin{eqnarray*}
A &=& \left\{ \left.
\left[  \bv{x_0}{y_0}{z_0} \right]
\left[  \bv{x_1}{y_1}{z_1} \right]
        \bv{\ldots}{\ldots}{\ldots}
\left[  \bv{x_s}{y_s}{z_s} \right]
\left[  \bv{\ttt{\#}}{\ttt{\#}}{z_{s+1}} \right]
\left[  \bv{\ttt{\#}}{\ttt{\#}}{\ttt{\#}} \right]^* \ 
\right| \ 
\mathit{x} + \mathit{y} = \mathit{z}, 
\right.
\\
& &
\textrm{where}\quad\left.
 x = \sum_{i=0}^{s} x_i \!\cdot\! 2^i \,,\quad
   y = \sum_{i=0}^{s} y_i \!\cdot\! 2^i \,,\quad
   z = \sum_{i=0}^{s+1} z_i \!\cdot\! 2^i
\right\}
\end{eqnarray*}

\paragraph{Part B (binary multiplication) (extra credit).} Is the following language regular? (Prove
your answer.)
\begin{eqnarray*}
B &=& \left\{ \left.
\left[  \bv{x_0}{y_0}{z_0} \right]
\left[  \bv{x_1}{y_1}{z_1} \right]
        \bv{\ldots}{\ldots}{\ldots}
\left[  \bv{x_s}{y_s}{z_s} \right]
\left[  \bv{\ttt{\#}}{\ttt{\#}}{z_{s+1}} \right]
        \bv{\ldots}{\ldots}{\ldots}
\left[  \bv{\ttt{\#}}{\ttt{\#}}{z_{t}} \right]
\left[  \bv{\ttt{\#}}{\ttt{\#}}{\ttt{\#}} \right]^* \ 
\right| \ 
\mathit{x} \cdot \mathit{y} = \mathit{z}, 
\right.
\\
& &
\textrm{where}\quad\left.
 x = \sum_{i=0}^{s} x_i \!\cdot\! 2^i \,,\quad
   y = \sum_{i=0}^{s} y_i \!\cdot\! 2^i \,,\quad
   z = \sum_{i=0}^{t} z_i \!\cdot\! 2^i
\right\}
\end{eqnarray*}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\end{document}
