\documentclass[]{article}
% Required packages.
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage{amssymb,amsmath}
\usepackage{color}
\usepackage{tikz}
\usepackage[utf8]{inputenc}
\usepackage{dsfont}
% 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 3}
\author{due 09/19 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.
Each problem is worth 20 points.
\section{Problem 1}
Let $M$ be a non-deterministic finite automaton. Show that there
exists a non-deterministic finite automaton $M'$ with the same
language as $M$, the same number of states as $M$, but without any
$\varepsilon$-transitions.
\section{Problem 2}
For a word $w=x_1\ldots x_n\in\Sigma^*$, define the \emph{reverse} of $w$, $w^R$, to be $x_n\cdots x_1$.
Let $L\subseteq\Sigma^*$ be a regular language.
Show that the reverse language $L^R:=\{w^R \mid w\in L\}$ is also regular.
\section{Problem 3}
Let $L\subseteq\Sigma^*$ be a regular language.
Show that the cycle language,
$$\mathrm{cycle}(L) = \{w_2 w_1 \mid w_1w_2\in L\},$$
is also regular.
\section{Problem 4}
Let $L\subseteq \Sigma^\ast$ be some language over $\Sigma$, not necessarily regular. Define an equivalence relation $\sim_L$ on $\Sigma^\ast$, the set of finite strings over $\Sigma$, by saying that $u\sim_L v$ if and only if for any $w\in\Sigma^\ast$, either both $uw$ and $vw$ are in $L$ or neither is. \\
\begin{tabular}{lp{11cm}}
(\textit{a}) & Suppose that $L_M$ is the language accepted by some DFA $M$. Show that the number of $\sim_{L_M}$-equivalence classes is finite. (Hint: Consider the state that $M$ will be in after reading a given string $u$.) \\
\\
(\textit{b}) & Consider the language $L_\text{match}=\{a^n b^n \mid n\geq 0\}$. Show that there are infinitely many $\sim_{L_\text{match}}$-equivalence classes. \\
\\
(\textit{c}) & Show that if for some language $L$, there are only finitely many $\sim_L$-equivalence classes, then $L$ is regular.
\\
\end{tabular}
\section{Problem 5}
\begin{tabular}{lp{11cm}}
(\textit{a}) &
For languages $A, B\subseteq \Sigma^*$, the \emph{perfect shuffle} of $A$ and $B$
is the language
\begin{eqnarray*}
\small \{x_1y_1\cdots x_ky_k &\mid& x_1\cdots x_k\in A \text{ and }y_1\cdots y_k\in B,\\
& & \text{symbols }x_1,\ldots,x_k,y_1,\ldots,y_k\in \Sigma\}
\end{eqnarray*}
Show that if $A$ and $B$ are regular, then the perfect shuffle of $A$
and $B$ is also regular. \\
\\
(\textit{b}) & For languages $A, B\subseteq \Sigma^*$, the \emph{shuffle} of $A$ and $B$
is the language
\begin{eqnarray*}
\small \{u_1v_1\cdots u_kv_k &\mid& u_1\cdots u_k\in A \text{ and }v_1\cdots v_k\in B,\\
& & \text{strings }u_1,\ldots,u_k,v_1,\ldots,v_k\in \Sigma^\ast\}
\end{eqnarray*}
Show that if $A$ and $B$ are regular, then the shuffle of $A$
and $B$ is also regular. \\
\end{tabular}
\end{document}