\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 January 31, 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}
\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}
For each of the following languages, construct a DFA that
accepts the language. In all cases, the alphabet is $\{0,1\}$.
For each DFA, justify correctness.
\noindent {\bf (\arabic{ques}.1)}
$\{ w \in \{0,1\}^* : w \mbox{ starts with 1 and ends with 0} \}$.
\noindent {\bf (\arabic{ques}.2)}
$\{ w \in \{0,1\}^*: \mbox{ every odd position in $w$ is 1}
\}$. The positions are numbered
$1,2,3,\ldots$
\noindent {\bf (\arabic{ques}.3)}
$\{ w \in \{0,1\}^* : w \mbox{ has length at least 3 and its third
symbol is 0}
\}$.
\noindent {\bf (\arabic{ques}.4)}
$\{ \epsilon , 0 \}$.
\end{question}
\begin{question}
For each of the following languages, construct an NFA that
accepts the language.
In all cases, the alphabet is $\{0,1\}$.
For each NFA, justify correctness.
\noindent {\bf (\arabic{ques}.1)}
$\{ w : w \mbox{ contains the substring 11001} \}$.
\noindent {\bf (\arabic{ques}.2)}
$\{ w : w \mbox{ has length at least 2 and does not end with 10}
\}$.
\noindent {\bf (\arabic{ques}.3)}
$\{ w : w \mbox{ begins with 1 or ends with 0} \}$.
\end{question}
\begin{question}
Let $A$ be a language over the alphabet $\Sigma = \{0,1\}$, and
let $\bar{A}$ be the \emph{complement} of $A$. Thus, $\bar{A}$ is the
language consisting of all binary strings that are not in $A$.
Assume that $A$ is a regular language.
Let $M = ( Q , \Sigma , \delta , q , F )$ be a nondeterministic finite
automaton (NFA) that accepts $A$.
Consider the NFA $N = ( Q , \Sigma , \delta , q , \bar{F} )$, where
$\bar{F} = Q \setminus F$ is the complement of $F$. Thus, $N$ is obtained
from $M$ by turning all accept states into nonaccept states, and turning
all nonaccept states into accept states.
\noindent {\bf (\arabic{ques}.1)}
Is it true that the language accepted by $N$ is equal to $\bar{A}$?
Justify your answer.
\noindent {\bf (\arabic{ques}.2)}
Assume now that $M$ is a deterministic finite automaton (DFA) that
accepts $A$. Define $N$ as above; thus, turn all accept states into
nonaccept states, and turn all nonaccept states into accept states.
Is it true that the language accepted by $N$ is equal to $\bar{A}$?
Justify your answer.
\end{question}
\begin{question}
Let $A$ and $B$ be two regular languages over the same alphabet
$\Sigma$. Prove that the difference of $A$ and $B$, i.e., the
language
\[ A \setminus B = \{ w : w \in A \mbox{ and } w \not\in B \}
\]
is a regular language. You may use any result that was proven in class.
\end{question}
\begin{question}
Use the construction given in class to convert the following NFA to an
equivalent DFA.
\begin{center}
\includegraphics[scale=0.80]{nfadfa1}
\end{center}
\end{question}
\begin{question}
Use the construction given in class to convert the following NFA to an
equivalent DFA.
\begin{center}
\includegraphics[scale=0.80]{nfadfa2}
\end{center}
\end{question}
\end{document}