\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 1
\end{center}
\noindent {\bf Due:} Thursday October 7, 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\_a1.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}
\capsulenew{{When specifying a finite automaton, it is sufficient to
draw the state diagram (because this diagram tells us what are the
alphabet, the set of states, the start state, the set of accept states,
and the transition function).
}}
\begin{question}
Write your name and student number.
\end{question}
\begin{question}
What is the language of the following DFA? The alphabet is $\{a,b\}$.
Justify your answer.
\begin{center}
\includegraphics[scale=0.80]{DFA}
\end{center}
\end{question}
\begin{question}
For each of the following two languages, construct a DFA that accepts the
language. In both cases, the alphabet is $\{a,b\}$. For each DFA, justify
correctness.
\noindent {\bf (\arabic{ques}.1)} $\{ abba \}$.
\noindent {\bf (\arabic{ques}.2)}
$\{ w \in \{a,b\}^* : \mbox{ $w$ does not contain $aa$ and $w$ does
not contain $ab$} \}$.
\end{question}
\begin{question}
Construct an NFA whose language is the set of all strings
$w \in \{a,b\}^*$ such that
\begin{itemize}
\item $w$ contains both $aa$ and $bb$, or
\item $w$ does not contain $aa$ and $w$ does not contain $bb$.
\end{itemize}
\end{question}
\begin{question}
Let $A$ be an arbitrary regular language over the alphabet $\Sigma$.
We define the language
\[ A_3 = \{ w \in A : \mbox{ the length of $w$ is a multiple of
three} \} .
\]
(Note that zero is a multiple of three.)
Prove that $A_3$ is a regular language.
You may use any result that was proven in class.
\end{question}
\begin{question}
Let $A$ be an arbitrary regular language over the alphabet $\Sigma$.
We define the language
\[ A' = \{ u \in \Sigma^* :
\mbox{ there exists a string $v \in \Sigma^*$ such
that $uv \in A$} \} .
\]
(In words, $A'$ consists of all prefixes of strings in $A$.)
Prove that $A'$ is a regular language.
\emph{Hint:} Let $M$ be a DFA that accepts $A$. How would you change the
state diagram of $M$ such that the resulting state diagram is a DFA
that accepts $A'$?
\end{question}
\begin{question}
Let $A$ be an arbitrary regular language over the alphabet $\Sigma$.
For two strings $x$ and $y$ in $\Sigma^*$, we say that the pair
$(x,y)$ is \emph{awesome}, if there exists a string $z$ in $\Sigma^*$
such that (i) $xz \in A$ and $yz \not\in A$ or
(ii) $xz \not\in A$ and $yz \in A$.
Let $M$ be a DFA that accepts the language $A$, let $(x,y)$ be an
awesome pair, let $q_x$ be the state that $M$ is in after having read
$x$, and let $q_y$ be the state that $M$ is in after having read $y$.
Prove that $q_x \neq q_y$.
\end{question}
\begin{question}
Use the previous question to prove that the language
\[ A = \{ a^n b^n : n \geq 0 \}
\]
is not regular.
\emph{Hint:} Use a proof by contradiction. If $n$ and $m$ are distinct
nonnegative integers, is the pair $(a^n , a^m)$ awesome?
You are not allowed to use the Pumping Lemma.
\end{question}
\newpage
\begin{question}
Use the construction given in class to convert the following NFA to an
equivalent DFA.
\begin{center}
\includegraphics[scale=0.80]{NFADFA}
\end{center}
\end{question}
\end{document}