\documentclass[11pt]{article}
\usepackage[letterpaper,margin=1in]{geometry}
\usepackage{amsmath,amsthm,amssymb,latexsym}
\usepackage{array,multirow,alltt,enumerate,bbm,eucal,graphicx}
\usepackage[colorlinks]{hyperref}
\usepackage{mathpazo,xcolor,stmaryrd,bussproofs,mathpartir}
\usepackage{tikz,pgfmath}
\usepgflibrary{shapes}
\usetikzlibrary{arrows,automata,backgrounds}

\setlength\parindent{0in}
\addtolength\parskip{1ex}
\setlength\fboxrule{.5mm}\setlength{\fboxsep}{1.2mm}
\newlength\courseheader
\courseheader=\textwidth
\addtolength\courseheader{-4mm}
\parindent=0pt
\parskip=1ex

%macro definitions

\newcommand\eps{\varepsilon}
\newcommand\Imp{\Rightarrow}
\renewcommand\hat{\widehat}

%environment definitions

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}


\begin{document}

\begin{center}
\framebox{\parbox\courseheader{\large Introduction to Theory of Computing\hfill Homework 1\\ 
CS 4810 Spring 25\hfill Your Name (yn4810), Partner Name (pn4810)}}
\end{center}
\medskip

This is a template you can use to help format your homework solutions.
\begin{enumerate}
\item
\begin{enumerate}
\item
If you have trouble, please ask for help on Ed.
\item
We will also release the \LaTeX\ source for the homework sets to get you started.
\end{enumerate}

\item
\begin{enumerate}[(i)]
\item
Here are two displayed equations. Use ampersands (\&) in the \texttt{align} or \texttt{align*} environment to space them attractively:
\begin{align*}
\hat\delta(s,\eps) &= s  &  \hat\delta(s,xa) &= \delta(\hat\delta(s,x),a)
\end{align*}
\item
You can also use ampersands (\&) to align equations vertically:
\begin{align}
\hat\delta(s,xy) &= \hat\delta(\hat\delta(s,x),y) \label{expression}\\
\hat\delta(s,xyz) &= \hat\delta(\hat\delta(\hat\delta(s,x),y),z) \nonumber
\end{align}
Here we have aligned them at the equal sign (=).
You can refer to expressions by giving them labels, e.g.\ \eqref{expression}.
\end{enumerate}

\item
Organize your proofs using lemmas and theorems. Use symmetry where appropriate.
\begin{lemma}
The operation $+$ is \emph{monotone} with respect to $\le$; that is, for all $a,b,c$, if $a\le b$, then
\begin{enumerate}[(i)]
\item
$a+c \le b+c$, 
\item
$c+a \le c+b$.
\end{enumerate}
\end{lemma}

\begin{proof}
For (i),
\begin{align*}
a \le b
&\Imp a+b = b && \text{definition of $\le$}\\
&\Imp a+b+c = b+c\\
&\Imp a+c+b+c = b+c && \text{idempotence, commutativity of +}\\
&\Imp a+c \le b+c && \text{definition of $\le$.}
\end{align*}
Property (ii) follows from (i) and the commutativity of +.
\end{proof}

\begin{theorem}
The operation $+$ is \emph{monotone} with respect to $\le$; that is, for all $a,b,c$, if $a\le b$, then
\begin{enumerate}[(i)]
\item
$ac \le bc$, 
\item
$ca \le cb$.
\end{enumerate}
\end{theorem}
\begin{proof}
For (i),
\begin{align*}
a \le b
&\Imp a+b = b && \text{definition of $\le$}\\
&\Imp (a+b)c = bc\\
&\Imp ac+bc = bc && \text{distributivity}\\
&\Imp ac \le bc && \text{definition of $\le$.}
\end{align*}
The argument for (ii) is symmetric.
\end{proof}

\clearpage

\item
There are three general ways to specify finite automata:
\begin{enumerate}[(A)]
\item
One can draw diagrams using the tikz automata library:
\begin{center}
\begin{tikzpicture}[->, >=stealth', auto, state/.style={circle, draw, inner sep=2pt}]
\small
\node[state, initial] (St0) {$0$};
\node[state, accepting] (St1) [right of=St0, node distance=2cm] {$1$};
\node[state] (St2) [below of=St0, node distance=1.732cm, xshift=1cm] {$2$};
\path (St0) edge[bend left] node {$a$} (St1);
\path (St1) edge[bend left] node {$b$} (St0);
\path (St1) edge[loop right] node {$a$} (St1);
\path (St0) edge node[swap] {$b$} (St2);
\path (St2) edge node[swap] {$b$} (St1);
\path (St2) edge[loop below] node {$a$} (St2);
\end{tikzpicture}
\end{center}
The accept states are indicated with a double circle. Tikz is very versatile; you can find documentation \href{https://ctan.mirrors.hoobly.com/graphics/pgf/base/doc/pgfmanual.pdf}{here}.

\item
You can also use \LaTeX\ tables:
\begin{align*}
\begin{array}{r@{\ }l|cc}
\multicolumn 2 c {} & a & b\\ \cline{3-4}
\text{start $\to$} & 0 & 1 & 2\\
& 1F & 1 & 0\\
& 2 & 2 & 1
\end{array}
\end{align*}

\item
\ldots\ or just write down all the components. For example, $M = (Q,\Sigma,\delta,s,F)$, where
\begin{itemize}
\item $Q = \{0,1,2\}$ 
\item $\Sigma = \{a,b\}$ 
\item $\delta(0,a) = 1$, $\delta(0,b) = 2$, $\delta(1,a) = 1$, $\delta(1,b) = 0$, $\delta(2,a) = 2$, $\delta(2,b) = 1$  
\item $s = 0$ 
\item $F = \{1\}$. 
\end{itemize}
Alternatively, you could write
\begin{align*}
M = (\{0,1,2\},\{a,b\},\delta,0,\{1\})
\end{align*}
where
\begin{align*}
\delta(s,a) &= \begin{cases}
1, & \text{if $s\in\{0,1\}$}\\
2, & \text{if $s=2$}
\end{cases}
&
\delta(s,b) &= \begin{cases}
2, & \text{if $s=0$}\\
0, & \text{if $s=1$}\\
1, & \text{if $s=2$}
\end{cases}\\
&& &= s-1 \bmod 3.
\end{align*}

\end{enumerate}
\end{enumerate}

\end{document}
