\documentclass[12pt]{article}

\usepackage{amsmath,amscd,amsbsy,amssymb,latexsym,url}
\usepackage{epsfig,graphicx,subfigure}
\usepackage{enumitem,balance,mathtools}
%\usepackage[labelsep=period, justification=justified, bf, width=1.3\linewidth, format=plain]{caption}
\usepackage{wrapfig}
\usepackage{tikz} \setlength\oddsidemargin{-0.05in}
\usetikzlibrary{calc} \setlength\evensidemargin{-0.05in}
%\usepackage{natbib}
\setlength\textheight{8.7in} \setlength\topmargin{-0.1in}
\setlength\textwidth{6.3in}
\usepackage{mathrsfs, euscript}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{exercise}{Exercise}[section]
%\newtheorem{solution}{section}

\setcounter{section}{1} \numberwithin{equation}{section}
\numberwithin{figure}{section}

\newenvironment{proof}[1][Proof:]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
\newenvironment{definition}[1][Definition:]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
\newenvironment{example}[1][Example:]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
\newenvironment{remark}[1][Remark:]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
\newenvironment{solution}[1][Solution:]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}

\newcommand{\qed}{\nobreak \ifvmode \relax \else
      \ifdim\lastskip<1.5em \hskip-\lastskip
      \hskip1.5em plus0em minus0.5em \fi \nobreak
      \vrule height0.4em width0.5em depth0.25em\fi}
\newcommand{\hw}[1]{#1}%includes solutions
%\newcommand{\hw}[1]{}
\newcommand{\indt}[1]{\begin{list}{\setlength\leftmargin{0.5in}}\item{}#1\end{list}\noindent}
\def\Prob{\text{Prob}}
\def\prob{\text{Prob}}
\begin{document}
\noindent

%========================================================================
\begin{center}
\textbf{\Large{Homework 12}} \vspace{2mm}

Mathematics in Computer Science
%John E. Hopcroft
\end{center}
\vspace{1mm}

\begin{enumerate}
\item Construct a deterministic finite automaton that accepts the set of all strings of 0's
and 1's where the number of 0's is even and the number of 1's is divisible by 3.

\item Construct a deterministic finite automaton that accepts the set of all strings of 0's
and 1's that have either two consecutive 0's or two consecutive 1's.

\item Let $M_1$ and $M_2$ be deterministic finite automata. Write out the formal definition of a DFA accepting
$L(M_1) \cap L(M_2)$.

\item Given a finite automaton $M = (\{A,B\}, \{0\}, \delta, A, F = \{B\})$ with two states $A$ and
$B$ and one accepting state $B$ with the transition function shown below prove by
induction that the automaton $M$ accepts the set of all odd length strings of 0's.
Note that the input alphabet of $M$ has only one symbol 0.

\begin{center}
\begin{tabular}{c|c}
 & 0\\
\hline
A & B \\
B & A
\end{tabular}
\end{center}
\end{enumerate}


%========================================================================
\end{document}
