\documentclass{article}
\usepackage{fullpage}

\input{macros}

\setlength{\parskip}{.4cm}
\setlength{\baselineskip}{15pt}
\setlength{\parindent}{0cm}

\author{}
\date{}

\begin{document}

\hrule
\begin{center}
{\LARGE \sc $\underline{\mbox{Problem Set 5}}$} \\
{\Large \sc CS 373: Theory of Computation}\\
\ \\
\begin{tabular}{ll}
Assigned: February 21, 2013 & Due on: February 28, 2013
\end{tabular}
\end{center}
\hrule

{\bf Instructions:} This homework has 3 problems that can be solved in
groups of size at most 3. Please follow the homework guidelines given
on the class website; submitions not following these guidelines will
not be graded. 

{\bf Recommended Reading:} Lecture 9, 10 and 11.

\begin{problem}{Proof}
Let $C = \{1^kx\: |\: x \in \{0,1\}^*,\ k \geq 1, \mbox{ and $x$
  contains at most $k$ $1$s}\}$. Using the pumping lemma, prove that
$C$ is not regular.\points{10}
\end{problem}

\begin{problem}{Comprehension+Design}
Let $L = \lang{1^*0(00 \cup 01 \cup 1)(0 \cup 1)^*}$.
\begin{enumerate}
\item List all the equivalence classes of $\equiv_L$. Prove that your
  answer is correct.\points{5}
\item Draw the minimum state DFA $M^L$ accepting $L$.\points{5}
\end{enumerate}
\end{problem}

\begin{problem}{Comprehension+Proof}
For a language $L \subseteq \Sigma^*$, define an equivalence
$\simeq_L$ on $\Sigma^*$ as follows
\[
x \simeq_L y \mbox{ iff } \forall z.\ zx \in L \leftrightarrow zy \in L
\]
Notice that this is a slightly different equivalence than $\equiv_L$
defined in Lecture 11. Prove that $L$ is regular iff $\simeq_L$ has
finitely many equivalence classes. \emph{Hint:} Can you see a
connection between $\simeq_L$ and $\equiv_{L^R}$, where $L^R$ refers
to the reverse of $L$?\points{10}
\end{problem}

\end{document}
