\documentclass[10pt]{article}

\usepackage[margin=1in]{geometry}
\usepackage[small]{titlesec}
\usepackage{palatino, mathpazo}
\usepackage{inconsolata}
\usepackage{amsmath, amssymb}
\usepackage{enumerate}
\usepackage{graphicx}
\usepackage[normalem]{ulem}
\usepackage[mathscr]{euscript}


\newcommand{\ds}{\displaystyle}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\LL}{\mathscr{L}}

\setlength{\parindent}{0pt}
\setlength{\parskip}{1.5ex}

\title{\sc Math 4931 / 5931 -- Special Topics: Theory of Computation and Formal Languages\\[10pt]Homework 1}
\author{
	Spring 2023\\[10pt]
	due Friday, February 10, \underline{by the beginning of class}
}
\date{}
\begin{document}
\maketitle

\begin{center} 
	\emph{This homework assignment was written in \LaTeX{}. You can find the source code on the course website.}
\end{center}

\textbf{\underline{You must explain your reasoning for all of your answers. Correct answers with no justification or}\\[5pt]\underline{explanation will not be accepted.}}

\textbf{Students enrolled in Math 4931: Complete any 6 out of the 7 problems.}\\
\textbf{Students enrolled in MSSC 5931: Complete all 7 problems.}\\


\begin{enumerate}

	\item Find a regular expression for the language $\LL_1$ of words over the alphabet $\{a,b\}$ that have no consecutive $aa$.
	\item Find a regular expression for the language $\LL_2$ of words over the alphabet $\{x,y,z\}$ that start and end with the same letter.
	\item Find a regular expression for the language $\LL_3$ of words over the alphabet $\{0, 1\}$ in which the letters alternate between $0$ and $1$---in other words, there are two $0$s in a row and no two $1$s in a row.
	\item Make up a language of words that you think might be regular, and then find a regular expression for it. Be creative!
	\item The \emph{reverse} of a word $w = w_1w_2\cdots w_n$, denoted $w^R$ is the word $w_n\cdots w_2w_1$ (i.e., just reverse the order of the letters in the word). If $\LL$ is a language, define the \emph{reverse} of $\LL$, denotes $\LL^R$ to be the set of reverses of words in $\LL$:
	\[
		\LL^R = \{w^R : w \in \LL\}.
	\]
	Prove that if $\LL$ is regular, then so is $\LL^R$.
	\item A regular expression for words over $\Sigma = \{a,b\}$ that contain the pattern $aab$ consecutively is
	\[
		\Sigma^*aab\Sigma^*.
	\]
	Find a regular expression for words over $\Sigma$ that \emph{don't} contain $aab$ consecutively.
	\item For each of the pairs below, decide whether the two regular expressions represent the same language, or different languages. As always, explain your reasoning!

	\begin{tabular}{rll}
		(a) & $(0\cup1)^*$ \hspace*{1in}& $0^* \cup 1^*$\\[5pt]
		(b) & $0(120)^*12$ & $01(201)^*2$\\[5pt]
		(c) & $\emptyset^*$ & $\varepsilon^*$\\[5pt]
		(d) & $(0^*1^*)^*$ & $(0^*1)^*$\\[5pt]
		(e) & $\{01, 0\}^*0$ & $0\{10, 0\}^*$
	\end{tabular}

\end{enumerate}
\end{document}


