\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 1}}$} \\
{\Large \sc CS 373: Theory of Computation}\\
\ \\
\begin{tabular}{ll}
Assigned: January 17, 2013 & Due on: January 24, 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. The website {\tt www.automatatutor.com} might be useful
to solve problem 3. It is a tool to teach students how to design DFAs
for languages. It has an easy user interface where you can draw
automata for problems and the tool will either say that your solution
is correct, or provide examples to help you fix your incorrect
solution. The languages in problem 3 are posed as ``problems'' on the
website. However, the website is only available until Monday, January
21, midnight.

{\bf Recommended Reading:} Lectures 1 and 2 and website {\tt
  http://www.automatatutor.com}

\begin{problem}{Comprehension+Proof}
\begin{enumerate}
\item Let $A = \setof{1,2,3}$, $B =
  \setof{\emptyset,\setof{1},\setof{2}}$, and $C =
  \setof{1,2,\setof{1,2}}$. Compute $A \cup B$, $A \cap B$, $B \cap
  C$, $A \cap C$, $A \times B$, $A \times C$, $C \setminus A$, $C
  \setminus B$, $A \times B \times C$, and $\powerset{B}$. Recall that
  $\powerset{A}$ denotes the \emph{power set} of $A$, and $A \setminus
  B$ denotes $A$ \emph{set difference} $B$.\points{5}
\item Prove for any two sets $A$ and $B$, $A \times B = B \times A$ if
  and only if $A = B$ or $A = \emptyset$ or $B = \emptyset$.\points{5}
\end{enumerate}
\end{problem}

\begin{problem}{Comprehension}
Consider the following DFA $M_0$ over the alphabet $\{0,1\}$.
\begin{figure}[h]
\begin{center}
\begin{tikzpicture}
\node[style=finalst](A) at (0,2) {$A$};
\node[style=autst](B) at (0,0) {$B$};
\node[style=autst](C) at (3,0) {$C$};
\node[style=autst](D) at (3,2) {$D$};
\initialst{A};
\curveltorabove{A}{D}{$0$};
\curvertolbelow{D}{A}{$1$};
\curvettobleft{A}{B}{$1$};
\curvebtotright{B}{A}{$0$};
\draw[->] (B) -- node[above]{$1$} (C);
\draw[->] (D) -- node[right]{$0$} (C);
\selfloopbelow{C}{$0,1$};
\end{tikzpicture}
\end{center}
\caption{DFA $M_0$ for Problem 2}
\end{figure}
\begin{enumerate}
\item Describe formally what the following are for automaton $M_0$: set
  of states, initial state, final states, and transition
  function.\points{4}
\item What are $\deltastr{M_0}(A,\emptystr)$,
  $\deltastr{M_0}(A,1011)$, $\deltastr{M_0}(B,101)$, and
  $\deltastr{M_0}(C,10110)$?\points{4}
\item What is $\lang{M_0}$? \points{1}
\item What is the language recognized if we change the initial state
  to $B$? What is the language recognized if we change the set of
  final states to be $\{B\}$ (with initial state $A$)?\points{1}
\end{enumerate}
\end{problem}

\begin{problem}{Design}
Design DFAs to recognize the following languages; the alphabet in each
case is $\setof{a,b}$. You need not prove that your construction is
correct, but your construction must be clear and understandable.
\begin{enumerate}
\item $L_1 = \setof{w \in \setof{a,b}^*\: |\: w \mbox{ starts with $a$
    and has an odd number of $ab$ substrings}}$. For example, $aaab
  \in L_1$ (has only 1 $ab$), $bab \not\in L_1$ (does not begin with
  $a$), and $abbab \not\in L_1$ (has 2 $ab$ substrings). \points{5}
\item $L_2 = \setof{w \in \{a,b\}^*\: |\: w \mbox{ starts with $ab$ or
  } |w| \mbox{ is not divisible by }3}$. For example, $abb \in L_2$
  (because it begins with $ab$), $baba \in L_2$ (because $|baba| = 4$
  is not divisible by $3$), and $bab \not\in L_2$. \points{5}
\end{enumerate}
\end{problem}

\end{document}
