\documentclass{article}

%
% title macros
%
\newcommand\myname{Prof. Nadeem Abdul Hamid}
\newcommand\course{CSC 320 Spring 2005}
\newcommand\hwnum{2}
\newcommand\duedate{Friday, February 4, 2005}

\newcommand\probtitle{
 \title{Homework \hwnum\ --\ Due: \duedate}\author{\myname\\\course}\date{}
 \maketitle}
\newcommand\solntitle{
	{\bf\flushright \myname\\\course\\\today\\Homework \hwnum\\}}


%
% local macros
%
\newcommand\powset[1]{\mathcal{P}(#1)}
\newcommand\problem{\section{}}



%
% main document
%
\begin{document}

\probtitle

\problem \textbf{\emph{Typeset only}} the statements of problems
(1.23), (1.24), and (1.25) in the Sipser textbook using \LaTeX. You do
not have to solve the 
problems -- just reproduce the statements of the problems as closely
as possible. Upload your \LaTeX source file to the Vikingweb.



\problem Solve Exercise 1.3 in Sipser: The formal description of a DFA
(deterministic finite automaton) $M$ is $(\{q_1, q_2, q_3, q_4, q_5\},
   \{\mathrm{u},\mathrm{d}\}, \delta, q_3, \{ q_3 \} )$, where $\delta$
is given by the following table. Give the state diagram of the
machine. 


\[\begin{array}{c|cc}
    	& \mathrm{u} 	& \mathrm{d} \\
 \hline
 q_1	& q_1	& q_2 \\
 q_2	& q_1	& q_3 \\
 q_3	& q_2	& q_4 \\
 q_4	& q_3	& q_5 \\
 q_5	& q_4	& q_5
  \end{array}\]



\problem Solve Exercise 1.4, parts (c), (h), (j), (k), and (l).

Give state diagrams of DFAs recognizing the following languages. In
all cases the alphabet is $\{ 0, 1 \}$.
\begin{itemize}
  \item $\{w | w$ contains the substring $0101$, i.e., $w=x0101y$ for
some $x$ and $y \}$.
  \item $\{w | w$ is any string except $11$ and $111 \}$.
  \item $\{w | w$ contains at least two $0$s and at most one $1 \}$.
  \item $\{ \epsilon, 0 \}$.
  \item $\{w | w$ contains an even number of $0$s, or exactly two $1$s$\}$.
\end{itemize}






\end{document}