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

\newcommand{\kgmcomment}[1]{}

\begin{document}
\headers{Math375}{Homework 10}{Due: Oct. 29, 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\}$.  Let $A$ be the language $\{w~|~\mbox{$w$ is an integer in binary notation and $w$ is divisible by $5$}\}$.  For example, $1010$ represents $1\cdot 2^3 + 0\cdot 2^2 + 1\cdot 2^1 + 0\cdot 2^0 = 8 + 2 = 10$, so $1010\in A$.  On the other hand, $01110$ represents $0\cdot 2^4 + 1\cdot 2^3 + 1\cdot 2^2 + 1\cdot 2^1 + 0\cdot 2^0 = 8 + 4 + 2 = 14$ so $01110\not\in A$.  Give a DFA that recognizes $A$.

\item Show that if $A$ and $B$ are regular languages, then $AB$ is a regular language.  Hint: given a DFA $M_1$ for $A$ and a DFA $M_2$ for $B$, describe how to use $M_1$ and $M_2$ to make an NFA for $AB$.  Why is it enough to make an NFA?

\item Let $G$ be the following graph.
\begin{center}
\begin{tikzpicture}
	\tikzstyle{vertex}=[circle,draw,minimum size=2.5ex]
	\node[vertex] at (-1,-1) (U1) {$u_1$} ;
	\node[vertex] at (5,-1) (U2) {$u_2$} ;
	\node[vertex] at (5,5) (U3) {$u_3$} ;
	\node[vertex] at (-1,5) (U4) {$u_4$} ;
	\node[vertex] at (1,1) (U5) {$u_5$} ;
	\node[vertex] at (3,1) (U6) {$u_6$} ;
	\node[vertex] at (3,3) (U7) {$u_7$} ;
	\node[vertex] at (1,3) (U8) {$u_8$} ;
	
	\draw (U1) -- (U2) -- (U3) -- (U4) -- (U8) -- (U7) -- (U6) -- (U5) -- (U1) -- (U4) (U5) -- (U8)  (U7) -- (U3) (U2) -- (U6) ;
	
\end{tikzpicture}
\end{center}
\begin{enumerate}
	\item Find two disjoint $4$-cycles in $G$.
	\item Find a $6$-cycle in $G$.
	\item Does $G$ contain an $8$-cycle?  If so, describe one.  If not, explain why not.
	\item Show how to color the vertices red and blue so that no edge has two endpoints with the same color.
	\item Does $G$ contain a $5$-cycle?  If so, describe one.  If not, explain why not.
\end{enumerate}

\kgmcomment{
\item Let $G$ be the graph whose vertices are the subsets of $\{1,2,3,4,5\}$ of size 2 with two vertices adjacent if and only if they are disjoint.  For example, $V(G) = \{\{1,2\}, \{1,3\}, \{1,4\}, \{1,5\}, \{2,3\}, \ldots, \{4,5\}\}$; we have that $\{1,2\}$ and $\{1,4\}$ are not adjacent, but $\{1,2\}$ and $\{3,5\}$ are adjacent.
\begin{enumerate}
	\item Draw a copy of $G$.
	\item Find two vertex-disjoint $5$-cycles in $G$.
\end{enumerate}
}

\end{enumerate}

\end{document}
