\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 --- Fall 2024 --- Assignment 1
\end{center}
\noindent {\bf Due:} Friday September 27, 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). However, you must explain the meaning of
the different states that you use.
}}
\newpage
\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\}$.
As always, justify your answer.
\noindent
\emph{Hint:} After having stared long enough at this DFA, you will
know the answer. Once you know the answer, it is not too difficult to
prove that your answer is correct.
\begin{center}
\includegraphics[scale=0.7]{DFA}
\end{center}
\end{question}
\begin{question}
Let $A$ be the language consisting of all strings over the alphabet
$\{a,b,c\}$ that are alphabetically sorted, i.e., all $a$'s are to the
left of all $b$'s, and all $b$'s are to the left of all $c$'s. Note that
the empty string $\varepsilon$ is in $A$. Also, strings in $A$ may have
no $a$'s or no $b$'s or no $c$'s.
\begin{itemize}
\item Construct a DFA with five states that accepts the language $A$.
As always, justify your answer.
\item Construct an NFA with three states that accepts the language $A$.
As always, justify your answer.
\end{itemize}
\end{question}
\begin{question}
Let $A$ be the language consisting of all strings over the alphabet
$\{a,b\}$ that contain $aa$ and do not contain $bb$.
Prove that $A$ is a regular language, without explicitly constructing a
DFA/NFA that accepts $A$. Instead, use properties that we have seen
in class.
\end{question}
\begin{question}
Let $A$ be a regular language over the alphabet $\{a,b\}$.
Define the following language
\[ B = \{ w : \exists \, x \in \{a,b\} \mbox{ such that } wx \in A \} .
\]
In words, $B$ is obtained by deleting the last symbol in every
non-empty string in $A$.
Prove that $B$ is a regular language.
\noindent
\emph{Hint:}
Let $M$ be an arbitrary DFA that accepts $A$. Show how to modify $M$ to
obtain a DFA that accepts the language $B$.
\end{question}
\begin{question}
Let $A$ be an arbitrary regular language and let $M$ be a DFA that
accepts $A$. Let $M'$ be the DFA obtained from $M$ by ``flipping the
states'': every accept state in $M$ is a non-accept state in $M'$,
and every non-accept state in $M$ is an accept state in $M'$.
We have seen in class that $M'$ accepts the complement
$\overline{A}$ of $A$.
Professor Taylor Swift claims that this ``flipping states'' construction
also works if $M$ is an NFA that accepts the language $A$.
Is Professor Swift's claim correct? As always, justify your answer.
\end{question}
\begin{question}
Let $A$ be the language consisting of all strings over the alphabet
$\{a,b\}$ that have an even length. Construct an NFA with three states
that accepts the language $A$ and in which the start state is not an
accept state. As always, justify your answer.
\end{question}
\begin{question}
Use the construction given in class to convert the following NFA
(with alphabet $\{a,b,c\}$) to an equivalent DFA.
\begin{center}
\includegraphics[scale=0.7]{NFADFA}
\end{center}
Show the full state diagram of the DFA; it has $2^3 = 8$ states.
Afterwards, simplify the diagram by removing states that cannot be
reached from the start state (in case this is possible).
\end{question}
\end{document}