\documentclass[12pt]{article}
\usepackage{fullpage}
\usepackage{graphicx}
\newcounter{ques}
\newenvironment{question}{\stepcounter{ques}{\noindent\bf Question \arabic{ques}:}}{\vspace{5mm}}
\begin{document}
\begin{center} \Large\bf
COMP 3803 --- Assignment 2
\end{center}
\noindent {\bf Due:} Thursday February 14, before 11:55pm.
\vspace{0.5em}
\noindent {\bf Assignment Policy:}
\begin{itemize}
\item Your assignment must be submitted as one single PDF file through
cuLearn.
\item Late assignments will not be accepted.
\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{1em}
\begin{question}
Give regular expressions describing the following languages.
In all cases, the alphabet is $\{0,1\}$. Justify your answers.
\begin{itemize}
\item $\{ w : w \mbox{ contains an even number of $0$s and each $0$ is
followed by at least one $1$} \}$.
\item $\{ w : w \mbox{ contains exactly two $0$s and at least two
$1$s} \}$.
\item $\{ w : \mbox{ every odd position in $w$ is $1$} \}$.
\end{itemize}
\end{question}
\begin{question}
Use the construction given in class to convert the regular expression
\[ \left( (0 \cup 1) (1 1)^* \cup 0 \right)^*
\]
to an NFA. The alphabet is $\{0,1\}$.
\end{question}
\begin{question}
Use the construction given in class to convert the following DFA to a
regular expression.
\begin{center}
\includegraphics[scale=0.50]{dfare}
\end{center}
\end{question}
\begin{question}
Let $R$ be a regular expression and let $A$ be the language described by
$R$. Explain how to obtain a regular expression that describes the
complement $\overline{A}$ of $A$. You may use any result that was proven
in class and Assignment~1.
\end{question}
\begin{question}
Prove that the following languages are not regular.
\begin{enumerate}
\item $\{ a^n b^n c^{2n} : n \geq 0 \}$.
\item $\{ a^{3^n} : n \geq 0 \}$. (Remark: $a^{3^n}$ is the
string consisting of $3^n$ many $a$'s.)
\item $\{ uvu : u \in \{a,b\}^* , u \neq \epsilon , v \in \{a,b\}^* \}$.
\item $\{ a^m b^n : m \geq 0 , n \geq 0 , m \neq n \}$. (Using the
Pumping Lemma for this one is a bit tricky. You can avoid using
the Pumping Lemma by combining results about the closure under
regular operations.)
\end{enumerate}
\end{question}
\begin{question}
Let $A$ be a language consisting of finitely many strings.
\begin{enumerate}
\item Prove that $A$ is a regular language.
\item Let $n$ be the maximum length of any string in $A$. Prove that
\emph{every} deterministic finite automaton (DFA) that
accepts $A$ has at least $n+1$ states. (\emph{Hint:} How is
the pumping length chosen in the proof of the Pumping Lemma?)
\end{enumerate}
\end{question}
\end{document}