\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 2}}$} \\
{\Large \sc CS 373: Theory of Computation}\\
\ \\
\begin{tabular}{ll}
Assigned: January 24, 2013 & Due on: January 31, 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 3 and 4.

\begin{problem}{Design+Proof}
Let $A_k \subseteq \{a,b\}^*$ be the collection of strings $w$ where
there is a position $i$ in $w$ such that the symbol at position $i$
(in $w$) is $a$, and the symbol at position $i+k$ is $b$. For example,
consider $A_2$ (when $k = 2$). $baab \in A_2$ because the second
position ($i = 2$) has an $a$ and the fourth position has a $b$. On
the other hand, $bb \not\in A_2$ (because there are no $a$s) and $aba
\not\in A_2$ (because none of the $a$s are followed by a $b$ 2
positions away).
\begin{enumerate}
\item Design a DFA for language $A_k$. Your formal description (by
  listing states, transitions, etc. and not ``drawing the DFA'') will
  depend on the parameter $k$ but should work no matter what $k$
  is; see lecture 2, last page for such an example.\points{5}
\item Prove that your DFA is correct when $k=2$.\points{5}
\end{enumerate}
\end{problem}

\begin{problem}{Comprehension}
Consider the following NFA $M_0$ over the alphabet $\{0,1\}$.
\begin{figure}[h]
\begin{center}
\begin{tikzpicture}
\node[finalst](A) at (0,0) {$A$};
\node[autst](B) at (2,0) {$B$};
\initialst{A};
\selfloopabove{A}{$0$};
\curveltorabove{A}{B}{$0,1$};
\curvertolbelow{B}{A}{$1$};
\end{tikzpicture}
\end{center}
\caption{NFA $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,010)$, $\deltastr{M_0}(A,101)$, 
  $\deltastr{M_0}(A,1101)$, and $\deltastr{M_0}(B,10)$?\points{4}
\item What is $\lang{M_0}$? You don't have to prove your
  answer. \points{2}
\end{enumerate}
\end{problem}

\begin{problem}{Design+Proof}
Consider the language $A_2 \subseteq \{a,b\}^*$, from problem 1, which
was defined to be the collection of strings $w$ where there is a
position $i$ in $w$ such that the symbol at position $i$ (in $w$) is
$a$, and the symbol at position $i+2$ is $b$.
\begin{enumerate}
\item Design an NFA for language $A_2$ that has at most 4 states. You
  need not prove that your construction is correct, but the intuition
  behind your solution should be clear and understandable.\points{5}
\item Prove that any DFA recognizing $A_2$ has at least 5
  states.\points{5}
\end{enumerate}
\end{problem}

\end{document}
