%&latex
\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 5\par}
\vspace{2ex}

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\paragraph{Exercise 1} Are the  following two DFAs equivalent? ``$\to$" and ``*" is used to denote start and accept state here. Justify your conclusion. 
\begin{center}
\begin{tabular}{|c|c|c|}\hline
 & 0 & 1 \\\hline
\to A & B & F \\\hline
B & G & C \\\hline
*C & A & C \\\hline
D  & C & G \\\hline
E & H & F \\\hline
F & C & G \\\hline
G & G & E \\\hline
H & G & C \\\hline
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{|c|c|c|}\hline
 & 0 & 1 \\\hline
\to A & G & C \\\hline
B& B & A \\\hline
C  & D & B \\\hline
*D & A & D \\\hline
G & B & D \\\hline

\end{tabular}
\end{center}




\paragraph{Exercise 2}$\Sigma=\{0,1\}$,   build a two-way finite automaton that recognizes the following
language:
\[
\{w\Sigma^*w^R\ |\ w\in \Sigma^{100\}
\]
Try to minimize the number of states of the automata. At least how many states does
a minimum DFA have for the same language?
\paragraph{Exercise 3} Given the following Context
Free Grammar:

\[
S\to AB\ |\ CD
\]
\[
A\to \texttt{a}A\ |\ \epsilon 
\]
\[
B\to \texttt{b}B\texttt{c}\ |\ E\ |\ \texttt{c}D
\]
\[
C\to \texttt{a}C\texttt{b}\ |\ E\ |\ \texttt{a}A
\]
\[
D\to \texttt{c}D\ |\ \epsilon
\]
\[
E\to \texttt{b}E\ |\ \texttt{b}
\]

Please answer the following question:
\begin{enumerate}
\item What are the variables?
\item What are the terminals?
\item Which is the start variable?
\item Give three strings in the language.
\item Give three strings not in the language.
\item Is ``aaabbcc''in the language?
\item Give a description of the language in English.

\end{enumerate}
\paragraph{Exercise 4} Make an OBDD for the boolean function 
\[
        x_1 \xorl x_2 \xorl x_3.
\]
Hint: This is the parity function; it is true if and only if an odd number of
variables are true.

\paragraph{Exercise 5 (bonus)} Is $\{ (\texttt{d}^*\texttt{c})^m(\texttt{c}^*\texttt{d})^m\
|\  m\geq 1
}\}$ a regular language? Prove  your conclusion.
} 



\end{document}
