\documentclass[11pt]{article}
\usepackage{jeffe,handout,multicol,tikz}
\usetikzlibrary{arrows,automata}
\usepackage[latin1]{inputenc}

\newcommand{\kgmcomment}[1]{}

\begin{document}
\headers{Math375}{Homework 8}{Due: Oct. 8, 2015}

%\makeatletter
%\def\@oddfoot{\hfill \tikz \node[draw] {over} ; }
%\makeatother

\makeatletter
\def\@oddfoot{}
\makeatother

%\noindent
%\hfill Name: \underline{\hspace{3.5in}} 

%\begin{flushright}
%Name: \underline{\hspace{3.5in}} \\
%\end{flushright}
%\hrule

\def\columnseprule{0.4pt}

\noindent
\textbf{Directions:} You may work to solve these problems in groups, but all written work must be your own.  \textbf{Show your work}; See ``Guidelines and advice'' on the course webpage for more information.

\begin{enumerate}

\item Let $\Sigma=\{0,1\}$ and let $M$ be the automaton pictured below.
\begin{center}
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm,
                    semithick,initial text={}]
	\tikzstyle{every state}=[draw]
	
	\node[initial,state] (A) {$q_1$} ;
	\node[state] (B) [right of=A] {$q_2$} ;
	\node[state] (C) [below of=A] {$q_3$} ;
	\node[accepting,state] (D) [right of=C] {$q_4$} ;
	
	\draw (A) edge node {$0$} (B)
			  edge[swap] node {$1$} (C) 
		  (B) edge[loop above] node {$0$} ()
		      edge node {$1$} (D)
		  (C) edge[swap] node {$0$} (D)
		      edge[loop below] node {$1$} ()
		  (D) edge[loop below] node {$0,1$} () ;
\end{tikzpicture}
\end{center}
\begin{enumerate}
	\item List the sequence of states of $M$ on input $1101$.  Is $1101\in L(M)$?
	\item Give an English description for $L(M)$.
\end{enumerate}

\item {} Let $\Sigma=\{a,b\}$.  For each language $A$ below, construct an automaton $M$ that recognizes it.
\begin{enumerate}
	\item $\{w~|~\mbox{$w$ has at most $1$ $b$}\}$.
	\item $\{w~|~\mbox{$w$ the number of $a$'s in $w$ is divisible by 3}\}$
	\item $\{w~|~\mbox{$w$ has at most $1$ $b$ and the number of $a$'s is divisible by $3$}\}$.
\end{enumerate}

\item {} Let $\Sigma=\{a,b\}$ and let $M$ be the automaton pictured below (from Sipser 1.1).
\begin{center}
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm,
                    semithick,initial text={}]
	\tikzstyle{every state}=[draw]

	\node[initial,state] (Q1) at (150:2cm) {$q_1$} ;
	\node[accepting,state] (Q2) at (30:2cm) {$q_2$} ;
	\node[state] (Q3) at (270:2cm) {$q_3$} ;
	
	\draw (Q1) edge[loop above] node {$b$} ()
			   edge[bend left] node {$a$} (Q2) 
		  (Q2) edge[bend left] node {$a,b$} (Q3) 
		  (Q3) edge[bend left] node {$b$} (Q1)
		       edge[bend left] node {$a$} (Q2) ;
\end{tikzpicture}
\end{center}
\begin{enumerate}
	\item Give a simple English description for $L(M)$.
	\item Two automatas are \emph{equivalent} if their languages are equal.  The automaton above has $3$ states but is equivalent to an automaton with only 2 states.  Construct an automaton with $2$ states that is equivalent to $M$.
\end{enumerate}

\end{enumerate}
\end{document}
