\documentclass[12pt]{article}

\usepackage{tikz}
\usetikzlibrary{automata,positioning,arrows}

\begin{document}

\newif{\ifshowsoln}
%\showsolntrue % comment out to NOT show solution inside \ifshowsoln and \fi blocks.

\centerline{\bf Homework 1 Morally Due Feb 5}

{\bf WARNING: THIS HW IS TWO PAGES LONG!!!!!!!!!!!!!!!!!!!!!}

\begin{enumerate}
\item
(10 points)
When will the midterm be (give day and time)?
When will the final be (give day and time)?
By when do you have to tell Dr.\ Gasarch that
you cannot make the midterm? The final?

\item
(30 points)
The alphabet is $\{0,\ldots,9\}$.
We interpret the input as a base 10 natural number, read \emph{right to left}.
So the number 29139 will be read 9-3-1-9-2.

\begin{enumerate}
\item
(15 points)
Give the diagram for a finite automata classifier that determines, given $w$, 
what $w$ is congruent to mod 4.
How many states does it have?
\item
(15 points)
Give the diagram for a finite automata that just determines, given $w$, 
if $w\equiv 0 \pmod 4$, which has LESS STATES then the one
you had in the first part (don't be obnoxious and purposely do
an awful finite automata for the first one).
\end{enumerate}


\item
(30 points)
Same conventions as in the last problem.
\begin{enumerate}
\item
(5 points) Compute 

$10^0 \pmod {11}$

$10^1 \pmod {11}$

$10^2 \pmod {11}$

etc. until you spot a pattern. What is the pattern?

\item
(25 points)
Describe a finite automata classifier that determines, given $w$, 
what $w$ is congruent to mod 11. NOTE- the diagram would be very hard to
draw, so just describe it.
How many states does it have?
\item
(0 points) Think about but don't turn in: Do you think that mod 11 has a trick that
you could easily use?
\item
(0 points) Think about but don't turn in: Would a finite automata that just,
given $w$, determines is $w\equiv 0 \pmod{11}$ have LESS states
than the classifier?
\end{enumerate}

\centerline{\bf GO TO NEXT PAGE FOR THE REST OF THE HW}
\newpage

\item
(30 points) 
The alphabet is $\{0,\ldots,8\}$.
We interpret the input as a base 9 natural number, read \emph{right to left}. So the number 28138
will be read 8-3-1-8-2.

\begin{enumerate}
\item
(15 points)
Give the diagram for a finite automata classifier that determines, given $w$, 
what $w$ is congruent to mod 3.
How many states does it have?
\item
(15 points)
Give the diagram for a finite automata classifier that determines, given $w$, 
what $w$ is congruent to mod 4.
How many states does it have?
\end{enumerate}
\end{enumerate}
\end{document}