\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 4}}$} \\
{\Large \sc CS 373: Theory of Computation}\\
\ \\
\begin{tabular}{ll}
Assigned: February 7, 2013 & Due on: February 14, 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:} Lectures 7 and 8.

\begin{problem}{Comprehension+Design}
Consider the language $L = \overline{\lang{(abb^*)^*}}$.
\begin{enumerate}
\item Construct a DFA recognizing $L$. You need not prove that your
  construction is correct. If you construct it using the algorithms
  described in class then you should show all your steps. If you
  construct the automaton directly then you should explain the
  intuition behind your construction clearly.\points{5}
\item Construct a regular expression for the language $L$. Again you
  don't need to prove your regular expression to be correct, but you
  should show all the steps in the construction.\points{5}
\end{enumerate}
\end{problem}

\begin{problem}{Comprehension+Design+Proof}
For any string $w = w_1w_2\cdots w_n \in \Sigma^*$ (with $w_i \in
\Sigma$), the reverse of $w$, denoted as $w^R$, is the string $w$ in
reverse order, i.e., $w^R = w_nw_{n-1}\cdots w_1$. For a language $A
\subseteq \Sigma^*$, let $A^R = \{w^R\: |\: w \in A\}$. 
\begin{enumerate}
\item Given a DFA $M$, construct an NFA that recognizes
  $(\lang{M})^R$.\points{5}
\item Prove that the NFA constructed in the previous part is
  correct.\points{5}
\end{enumerate}
\end{problem}

\begin{problem}{Comprehension+Design+Proof}
For languages $A \subseteq \Sigma^*$ and $B \subseteq \Sigma^*$,
define the \emph{avoids} operation as follows.
\[
A\: \mbox{avoids}\: B = \{w \in A\: |\: w \mbox{ doesn't contain any
  string in $B$ as substring}\}
\]
\begin{enumerate}
\item Let $A = \{1001,1111\}$ and $B = \{01,10\}$. What is
  $A\:\mbox{avoids}\: B$?\points{1}
\item Let $A = \lang{(0\cup 1)^*}$ and $B = \lang{1^*}$. What is
  $A\:\mbox{avoids}\: B$?\points{1}
\item Prove that if $A$ and $B$ are regular then $A\:\mbox{avoids}\:
  B$ is regular. You can either construct a DFA/NFA/regular expression
  for $A\:\mbox{avoids}\: B$ (and then you don't have to prove that
  your construction is correct) or use previously established closure
  properties to prove this result.\points{8}
\end{enumerate}
\end{problem}

\end{document}
