\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}