\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 2022\hfill Due Tuesday, 1 February 2022}}
\end{center}
\medskip

\pagestyle{empty}

\begin{enumerate}
\item
Let $M = (Q,\Sigma,\delta,s,F)$ be an arbitrary DFA. Prove that
for all $x,y\in\Sigma^*$ and $q\in Q$,
\begin{align*}
\hat\delta(q,xy) &= \hat\delta(\hat\delta(q,x),y),
\end{align*}
where $\hat\delta$ is the extended version of $\delta$ defined on all
strings as described in class. (\emph{Hint}. Induction on $|y|$.)

\item
Design deterministic finite automata for each of the following sets:
\begin{enumerate}
\item
the set of strings in $\{0,1,2\}^*$ not containing the substring 221;
\item
the set of strings in $\{a\}^*$ whose length is divisible by either 4 or 6;
\item
the set of strings $x\in\{0,1\}^*$ such that $\#0(x)\cdot\#1(x)$ is even;
\item
the set of strings over the alphabet $\{a,b\}$ containing at least
three occurrences of two consecutive $a$'s, overlapping permitted
(for example, the string $aaaa$ should be accepted).
\end{enumerate}
In each case try to minimize the number of states.
The minimum possible number of states is (a) 4, (b) 12, (c) 4, (d) 7.

\item
Consider the following two deterministic finite automata.
\begin{align*}
\begin{array}{r@{\ }l|cc}
\multicolumn 2 c {} & a & b\\ \cline{3-4}
\to & 0 & 0 & 1\\
    & 1F & 0 & 1
\end{array}
&&
\begin{array}{r@{\ }l|cc}
\multicolumn 2 c {} & a & b\\ \cline{3-4}
\to & 0F & 0 & 1\\
    & 1 & 2 & 0\\
    & 2 & 1 & 2
\end{array}
\end{align*}
Use the product construction to produce deterministic automata
accepting (a) the intersection, and (b) the union of the two sets
accepted by these automata.

\item
Let $\Sigma$ be a finite alphabet and let $A\subseteq\Sigma^*$. Prove that $A^*$ is the smallest subset $X$ of $\Sigma^*$ such that
\begin{align*}
\{\eps\}\cup A\cup XX &\subseteq X.
\end{align*}
That is,
\begin{enumerate}[(i)]
\item
$A^*$ satisfies the set inequality $\{\eps\}\cup A\cup A^* A^*\subseteq A^*$; and
\item
if $B$ is any other subset of $\Sigma^*$ such that $\{\eps\}\cup A\cup BB\subseteq B$, then $A^*\subseteq B$.
\end{enumerate}

\emph{Hint}. First prove the following \emph{monotonicity lemma}: For $B,C,D\subseteq\Sigma^*$, if $C\subseteq D$ then $BC\subseteq BD$ and $CB \subseteq DB$. You may use basic set-theoretic facts (e.g., $B\cup C\subseteq D$ iff $B\subseteq D$ and $C\subseteq D$) without proof, but be clear about what facts you are using.
\end{enumerate}

\end{document}
