% CMPU 240 Assignment 2 Template

%
% Prelude
%

\documentclass[12pt]{exam}
\usepackage{enumerate}

% Change the default fonts. Comment out if you have issues.
\usepackage[sc]{mathpazo}
% Palladio needs more leading (space between lines)
\linespread{1.05}
\usepackage[T1]{fontenc}

\usepackage[fleqn]{amsmath}

\usepackage[md]{titlesec}

\usepackage{tikz}
\usetikzlibrary{automata,positioning,arrows}
\tikzset{
  shorten >=1pt,>=stealth',node distance=3.5cm,
  on grid,auto,semithick,double distance=1.25pt
}

% For marking inputs to finite automata, rather than typing out `texttt`.
\newcommand{\ipt}[1]{\texttt{#1}}

\newcommand{\ep}{\varepsilon}

% Checkmark and X-mark commands
\usepackage{pifont}
\newcommand{\cmark}{\ding{51}}
\newcommand{\xmark}{\ding{55}}

\header{CMPU\,240 Assignment 2}{}{
  \thepage\ of \numpages}

\pagestyle{head}


%
% Exercises
%

\begin{document}


\section*{Exercise 1}

It may be surprising how important the empty string and the empty language
are in language theory.
% Consider what mathematics would be like without the number 0!
This exercise makes sure you have a clear understanding of these
concepts.

\begin{enumerate}[a.]
\item Is there any language $L$ where $\ep \in L$? If so, give an
  example of one. If not, explain why not.

  \begin{quote}
    \textbf{Answer}:

    \textbf{Evaluation}:

    \textbf{Corrections and comments}:

  \end{quote}

\item Is there any language $L$ where $\ep \notin L$? If so, give
  an example of one. If not, explain why not.

  \begin{quote}
    \textbf{Answer}:

    \textbf{Evaluation}:

    \textbf{Corrections and comments}:

  \end{quote}

\item Is there any language $L$ where $\ep \subseteq L$? If so,
  give an example of one. If not, explain why not.

  \begin{quote}
    \textbf{Answer}:

    \textbf{Evaluation}:

    \textbf{Corrections and comments}:

  \end{quote}

\item Does $\emptyset = \ep$? Briefly explain your answer.

  \begin{quote}
    \textbf{Answer}:

    \textbf{Evaluation}:

    \textbf{Corrections and comments}:

  \end{quote}

\item Does $\emptyset = \{\ep\}$? Briefly explain your answer.

  \begin{quote}
    \textbf{Answer}:

    \textbf{Evaluation}:

    \textbf{Corrections and comments}:

  \end{quote}
\end{enumerate}


\break


\section*{Exercise 2}

Recall that the formal mathematical definition of a deterministic finite
automaton (DFA) is a 5-tuple $(Q, \Sigma, \delta, q_0, F)$, where:
\begin{itemize}
\item $Q$ is a finite set whose elements are called \emph{states};
\item $\Sigma$ is a non-empty finite set whose elements are called
  \emph{characters};
\item $\delta: Q \times \Sigma \rightarrow Q$ is the \emph{transition
  function}, described below;
\item $q_0 \in Q$ is the start state;
\item $F \subseteq Q$ is the set of accept states.
\end{itemize}
When we've drawn DFAs, we've represented the transitions by arrows
labeled with characters. In this formal definition, the transition
function $\delta$ is what specifies these transitions. Specifically, for
any state $q \in Q$ and any symbol $\alpha \in \Sigma$, the transition
from state $q$ on symbol $\alpha$ is given by $\delta(q, \alpha)$.

This question explores some properties of this definition:

\begin{enumerate}[a.]
\item Is it possible for a DFA to have no states? If so, define a
  DFA with no states as a 5-tuple and explain why it meets the above
  requirements. If not, explain why this is not possible.

  % To define a machine using a 5-tuple, use this template:
  %
  %``Let $D = (Q, \Sigma, \delta, q_0, F)$, where $Q = \ldots$, $\Sigma =
  % \ldots$, etc.''
  %
  % For this problem, please don't define the transition function $\delta$
  % with a diagram or a table. Instead, define it like a mathematical
  % function.

  \begin{quote}
    \textbf{Answer}:

    \textbf{Evaluation}:

    \textbf{Corrections and comments}:

  \end{quote}

\item Is it possible for a DFA to have no \emph{accept} states?
  If so, define a DFA with no accept states as a 5-tuple,
  and explain why it meets the above requirements. If not, explain why
  this is not possible.

  \begin{quote}
    \textbf{Answer}:

    \textbf{Evaluation}:

    \textbf{Corrections and comments}:

  \end{quote}

\item In class, we said that a DFA must obey the rule that for any
  state and any symbol, there has to be exactly one transition defined on
  that symbol. What part of the definition guarantees this?

  \begin{quote}
    \textbf{Answer}:

    \textbf{Evaluation}:

    \textbf{Corrections and comments}:

  \end{quote}

\item Is it possible for a DFA to have an unreachable state (i.e., a
  state that is never entered, regardless of what string you run the
  DFA on)? If so, define a DFA with an unreachable state as a
  5-tuple, and explain why it meets the above requirements. If not,
  explain why this is not possible.

  \begin{quote}
    \textbf{Answer}:

    \textbf{Evaluation}:

    \textbf{Corrections and comments}:

  \end{quote}

\end{enumerate}


\break


\section*{Exercise 3}

%   While it's possible to do this completely deterministically, we want
%   you to use the guess-and-check approach from class, which will make it
%   easier!
Construct a nondeterministic finite automaton (NFA) to recognize the
language
\begin{quote}
  $\{w \in \Sigma^* \mid w$ ends in \ipt{a}, \ipt{bb}, or
  \ipt{ccc}$\}$,
\end{quote}
where $\Sigma = \{\ipt{a}, \ipt{b}, \ipt{c}\}$.

\begin{quote}
  \textbf{Answer}: \emph{Your solution for this exercise should be
    submitted as a CSV file generated by \ipt{tock}, using the
    provided Colab notebook.}


  \textbf{Evaluation}:

  \textbf{Corrections and comments}:

\end{quote}


\break


\section*{Exercise 4}

%   While a DFA for this language would require at least 64 states,
%   an NFA needs far fewer. Consider: What would you do if you knew
%   which character was going to appear at most twice? Embrace the
%   nondeterminism!
Construct a nondeterministic finite automaton (NFA) to recognize the
language
\begin{quote}
  $\{w \in \Sigma^* \mid$ some character in $\Sigma$ appears at most
  twice in $w\}$,
\end{quote}
where $\Sigma = \{\ipt{a}, \ipt{b}, \ipt{c}\}$.

\begin{quote}
  \textbf{Answer}: \emph{Your solution for this exercise should be
    submitted as a CSV file generated by \ipt{tock}, using the
    provided Colab notebook.}

  \textbf{Evaluation}:

  \textbf{Corrections and comments}:

\end{quote}


\end{document}
