\documentclass[12pt]{amsart}

\newcommand{\lra}{\longrightarrow}
\newcommand{\Z}{{\mathbf Z}}
\newcommand{\Q}{{\mathbf Q}}
\newcommand{\R}{{\mathbf R}}
\newcommand{\C}{{\mathbf C}}
\newcommand{\Proj}{{\mathbf P}}
\newcommand{\northpole}{{\mathbf n}}
\renewcommand{\Re}[1]{{\text Re}(#1)}
\renewcommand{\Im}[1]{{\text Im}(#1)}

\include{xy}
\xyoption{all}
\SelectTips{cm}{}
\CompileMatrices

\include{iJSepsf}
\newcommand{\graphillus}[3]{\epsfysize=#1truein
\vbox{\centerline{\epsffile{#2.eps}}\caption{#3}}}

\theoremstyle{plain}
\newtheorem{thm}{Theorem}[section]
\newtheorem{defn}[thm]{Definition}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{cor}[thm]{Corollary}

\begin{document}

\title{Assignment from Chapter 1 of Sipser}
\maketitle

{\bf Part 1 (due Monday 10-9): }Exercises
\begin{itemize}
\item 1.6cel (state diagrams of DFAs for specified languages),
\item 1.7bce (state diagrams of NFAs of specified size for specified
languages),
\item 1.13 (state diagrams of an NFA of a specified size for a specified
language, perhaps via the suggested trick),
\item 1.17 (NFA for a specified language, the corresponding DFA),
\item 1.19 (NFAs for specified REs),
\item 1.21 (REs for specified DFAs),
\item 1.28 (NFAs for specified REs),
\item 1.29 (pumping lemma),
\item 1.30 (pumping lemma).
\end{itemize}

\medskip

{\bf Part 2 (due Wednesday 10-25): }Problems
\begin{itemize}
\item 1.32 (machine to recognize flashcards),
\item 1.41 and 1.42 (shuffles),
\item 1.46 and 1.49 (regular and nonregular languages),
\item 1.54c[quoting parts a and b] (nuance of the Pumping Lemma),
\item 1.55efhij (minimum pumping length),
\item 1.60[give only the state diagram, not the formal description] and 1.61
(a DFA may need to be exponentially larger than the corresponding NFA).
\end{itemize}

\end{document}
