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

\newcommand{\kgmcomment}[1]{}

\begin{document}
\headers{Math375}{Homework 9}{Due: Oct. 22, 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\}$.  Give state diagrams of DFAs for the following languages.
\begin{enumerate}
	\item $\{w~|~\mbox{$w$ begins with a 1 and ends with a 0}\}$.
	\item $\{w~|~\mbox{$w$ has an even number of 1s or contains the substring 101}\}$
\end{enumerate}

\item Let $N$ be the NFA pictured below.
\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) {$1$} ;
	\node[accepting,state] (Q2) at (30:2cm) {$2$} ;
	\node[state] (Q3) at (270:2cm) {$3$} ;
	
	\draw 	(Q1)	edge[loop above] node {$a$} ()
					edge node {$b$} (Q2) 
					edge[bend right,swap] node {$a$} (Q3)
			(Q2)	edge[loop above] node {$a$} ()
					edge node {$b,\lambda$} (Q3)
			(Q3)	edge[bend right,swap] node {$b$} (Q1) ;
				
\end{tikzpicture}
\end{center}
\begin{enumerate}
	\item Which of the following strings are accepted by $N$?  Explain.  Strings: $\lambda$, $b$, $bb$, $bbb$, $bbbb$.
	\item Convert $N$ into an equivalent DFA.
\end{enumerate}

\item Let $\Sigma=\{0,1\}$, let $A=\{w~|~\mbox{$w$ ends in a 1}\}$, and let $B=\{w~|~\mbox{$w$ has odd length}\}$.  Construct a DFA with 4 states that recognizes the language $AB$.  (Hint: it may be easier to first construct an NFA, convert to a DFA, and then simplify the DFA.)
\end{enumerate}
\end{document}
