\documentclass[]{article}
% Required packages.
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage{amssymb,amsmath}
\usepackage{color}
\usepackage{tikz}
\usepackage[utf8]{inputenc}
\usepackage{dsfont}
\usepackage{enumerate}
% Some setup.
\setlength{\parindent}{0pt}
\setlength{\parskip}{6pt plus 2pt minus 1pt}
\setlength{\emergencystretch}{3em} % prevent overfull lines
\setcounter{secnumdepth}{0}
% Input data macros for \maketitle.
\title{CS 4810: Homework 4}
\author{due 09/26 11:59pm}
\date{(your name + netid)} % TODO: Fill in your own name and netID here.
% The actual document technically begins here.
\begin{document}
\maketitle
Collaborators: (names and netids)
% TODO: List the names and netIDs of everyone who collaborated with
% you on this homework here.
Problem 1 is worth 10 points.
Each of the remaining problems are worth 30 points.
\section{Problem 1}
Let $M$ be any non-deterministic finite automaton.
%
Let $M'$ be the automaton obtained from $M$ by adding an
$\varepsilon$-transition from each accept state to the start state
and making the start state an accept state.
%
Prove or give a counter-example to the statement $L(M')=L(M)^\ast$.
\section{Problem 2}
Give a regular expression for each of the following languages --- \emph{full
proofs are not necessary}:
\begin{enumerate}[a.]
\item The set of all binary strings that start with $0$, end with $1$,
and have at most three $1$'s.
\item The set of all binary that have an odd number of $1$'s and
contain $00$ as a substring.
\item The set of all binary strings that do not contain the substring $001$.
\end{enumerate}
\newpage
\section{Problem 3}
Give a non-deterministic finite automaton for each of the following
regular expressions over the alphabet $\{0,1\}$ --- \emph{full
proofs are not necessary}:
\begin{enumerate}[a.]
\item $0(011)^*\cup 1$.
\item $00^*\cup 01(01)^*$.
\item $(0 \cup 11^*)00^*11^*$.
\end{enumerate}
\section{Problem 4}
For each of the following languages, prove or disprove that the
language is regular:
\begin{enumerate}[a.]
\item $\{ 0^s1^t2^{\max\{s,t\}} \mid \text{integers }s,t\ge 0\}\subseteq \{0,1,2\}^*$.
\item $\{0^s1^{2t} \mid \text{integers }s,t\ge 0 \} \subseteq \{0,1\}^*$.
\item $\{0^s1^{2t}2^{3t} \mid \text{integers }s,t\ge 0\} \subseteq \{0,1,2\}^*$.
\end{enumerate}
\end{document}