\documentclass[12pt]{article}
\usepackage{fullpage}
\usepackage{graphicx}
\usepackage{fancybox}
\newcounter{ques}
\newenvironment{question}{\stepcounter{ques}{\noindent\bf Question \arabic{ques}:}}{\vspace{5mm}}
%%%%%%%%%%%%%% Capsule %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\capsulenew}[1]{\vspace{0.5em}
\shadowbox{%
\begin{minipage}{.90\linewidth}%
#1%
\end{minipage}}
\vspace{0.5em} }
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
\begin{center} \Large\bf
COMP 3803 --- Assignment 2
\end{center}
\noindent {\bf Due:} Thursday October 21, 23:59.
\vspace{0.5em}
\noindent {\bf Assignment Policy:}
\begin{itemize}
\item Your assignment must be submitted as one single PDF file through
Brightspace.
\begin{center}
\hfill\shadowbox{
\begin{minipage}{.90\linewidth}
{\textsf{Use the following format to name your file:
\[ {\tt LastName\_StudentId\_a2.pdf}
\]
}}
\end{minipage}
}
\end{center}
\item {\bf Late assignments will not be accepted. I will not reply to
emails of the type ``my internet connection broke down at
23:57'' or ``my scanner stopped working at 23:58'', or
``my dog ate my laptop charger''.}
\item You are encouraged to collaborate on assignments, but at the level
of discussion only. When writing your solutions, you must do so
in your own words.
\item Past experience has shown conclusively that those who do not put
adequate effort into the assignments do not learn the material and
have a probability near 1 of doing poorly on the exams.
\item When writing your solutions, you must follow the guidelines below.
\begin{itemize}
\item You must justify your answers.
\item The answers should be concise, clear and neat.
\item When presenting proofs, every step should be justified.
\end{itemize}
\end{itemize}
\vspace{0.5em}
\begin{question}
Write your name and student number.
\end{question}
\begin{question}
\begin{itemize}
\item Consider the language $A$ consisting of all binary strings that end
with an even, and non-zero, number of $0$s.
Give a regular expression that describes the language $A$.
As always, justify your answer.
\item What is the language described by the following regular expression:
\[ ( 0 \cup 1 )^* (00)^* 00 .
\]
As always, justify your answer.
\end{itemize}
\end{question}
\newpage
\begin{question}
Give regular expressions describing the following two languages.
In both cases, the alphabet is $\{a,b\}$. Justify your answers.
\begin{itemize}
\item $\{ w : \mbox{ the number of $a$'s in $w$ is a multiple of three}
\}$.
\item $\{ w : w \mbox{ does not contain $aaa$} \}$.
\end{itemize}
\end{question}
\begin{question}
Use the construction given in class to convert the regular expression
\[ ( a \cup b )^* aa (a \cup b )^*
\]
to an NFA. Do not simplify your NFA; just apply the construction rules
``without thinking''.
\end{question}
\begin{question}
Use the construction given in class to convert the following DFA to a
regular expression.
\begin{center}
\includegraphics[scale=0.70]{dfare}
\end{center}
\end{question}
\begin{question}
Let $A$ be a regular language with alphabet $\{a,b\}$, and let
\[ B = \{ uv : u \in A , v \in \{a,b\}^*, |v|=2 \} ,
\]
where $|v|$ denotes the length of the string $v$. Prove that $B$ is a
regular language. Your proof must use the fact that a language is
regular if and only if there exists a regular expression that describes
the language.
\end{question}
\begin{question}
Prove that the following languages are not regular.
\begin{enumerate}
\item $\{ a^n b a^m b a^{n+m} : n \geq 0 , m \geq 0 \}$.
\item $\{ w \in \{a,b\}^* : w \mbox{ is not a palindrome} \}$.
(Remark: A string $w = w_1 w_2 \cdots w_n$ is a palindrome, if
$w_1 w_2 \cdots w_n = w_n \cdots w_2 w_1$. For example, each of
$abba$, $\epsilon$, and $b$ is a palindrome.
\item $\{ ucu : u \in \{a,b\}^* \}$. (The alphabet is $\{a,b,c\}$.)
\item $\{ a b a^2 b a^3 b \cdots a^n b : n \geq 0 \}$.
\end{enumerate}
\end{question}
\end{document}