% 
% LaTeX Problem Set Template by Sachin Padmanabhan
% I created this when I was a freshman in CS 103,
% and I continue to use it to this day.
%
% Hope you enjoy!
%
% There may be problems with this template.
% If so, feel free to contact me.
%

% Updated for Summer 2019 by Amy Liu

\documentclass{article}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{mathdots}
\usepackage[pdftex]{graphicx}
\usepackage{fancyhdr}
\usepackage[margin=1in]{geometry}
\usepackage{multicol}
\usepackage{bm}
\usepackage{listings}
\PassOptionsToPackage{usenames,dvipsnames}{color}  %% Allow color names
\usepackage{pdfpages}
\usepackage{algpseudocode}
\usepackage{tikz}
\usetikzlibrary{automata,positioning}
\usepackage{enumitem}
\usepackage[T1]{fontenc}
\usepackage{inconsolata}
\usepackage{framed}
\usepackage{wasysym}
\usepackage[thinlines]{easytable}
\usepackage{wrapfig}
\usepackage{hyperref}
\usepackage{mathrsfs}
\usepackage{tabularx} % also loads 'array' package
\newcolumntype{C}{>{\centering\arraybackslash}X} % centered version of 'X' columns
\usepackage{diagbox}

\title{CS 103: Mathematical Foundations of Computing\\Problem Set \#5}
\author{Your Name(s) Here}
\date{\today}

\lhead{Your Name(s) Here}
\chead{Problem Set \#5}
\rhead{\today}
\lfoot{}
\cfoot{CS 103: Mathematical Foundations of Computing --- Summer 2019}
\rfoot{\thepage}

\newcommand{\abs}[1]{\lvert #1 \rvert}
\newcommand{\absfit}[1]{\left\lvert #1 \right\rvert}
\newcommand{\norm}[1]{\left\lVert #1 \right\rVert}
\newcommand{\eval}[3]{\left[#1\right]_{#2}^{#3}}
\renewcommand{\(}{\left(}
\renewcommand{\)}{\right)}
\newcommand{\floor}[1]{\left\lfloor#1\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil#1\right\rceil}
\newcommand{\pd}[1]{\frac{\partial}{\partial #1}}
\newcommand{\inner}[1]{\langle#1\rangle}
\newcommand{\cond}{\bigg|}
\newcommand{\rank}[1]{\mathbf{rank}(#1)}
\newcommand{\range}[1]{\mathbf{range}(#1)}
\newcommand{\nullsp}[1]{\mathbf{null}(#1)}
\newcommand{\repr}[1]{\left\langle#1\right\rangle}
\newcommand\VRule[1][\arrayrulewidth]{\vrule width #1}

\DeclareMathOperator{\Var}{Var}
\DeclareMathOperator{\tr}{tr}
\DeclareMathOperator{\Tr}{\mathbf{Tr}}
\DeclareMathOperator{\diag}{\mathbf{diag}}
\DeclareMathOperator{\dist}{\mathbf{dist}}
\DeclareMathOperator{\prob}{\mathbf{prob}}
\DeclareMathOperator{\dom}{\mathbf{dom}}
\DeclareMathOperator{\E}{\mathbf{E}}
\DeclareMathOperator{\Q}{\mathbb{Q}}
\DeclareMathOperator{\R}{\mathbb{R}}
\DeclareMathOperator{\var}{\mathbf{var}}
\DeclareMathOperator{\quartile}{\mathbf{quartile}}
\DeclareMathOperator{\conv}{\mathbf{conv}}
\DeclareMathOperator{\VC}{VC}
\DeclareMathOperator*{\argmax}{arg\,max}
\DeclareMathOperator*{\argmin}{arg\,min}
\DeclareMathOperator{\Ber}{Bernoulli}
\DeclareMathOperator{\NP}{\mathbf{NP}}
\DeclareMathOperator{\coNP}{\mathbf{coNP}}
\DeclareMathOperator{\TIME}{\mathsf{TIME}}
\DeclareMathOperator{\polytime}{\mathbf{P}}
\DeclareMathOperator{\PH}{\mathbf{PH}}
\DeclareMathOperator{\SIZE}{\mathbf{SIZE}}
\DeclareMathOperator{\ATIME}{\mathbf{ATIME}}
\DeclareMathOperator{\SPACE}{\mathbf{SPACE}}
\DeclareMathOperator{\ASPACE}{\mathbf{ASPACE}}
\DeclareMathOperator{\NSPACE}{\mathbf{NSPACE}}
\DeclareMathOperator{\Z}{\mathbb{Z}}
\DeclareMathOperator{\N}{\mathbb{N}}
\DeclareMathOperator{\EXP}{\mathbf{EXP}}
\DeclareMathOperator{\NEXP}{\mathbf{NEXP}}
\DeclareMathOperator{\NTIME}{\mathbf{NTIME}}
\DeclareMathOperator{\DTIME}{\mathbf{DTIME}}
\DeclareMathOperator{\poly}{poly}
\DeclareMathOperator{\BPP}{\mathbf{BPP}}
\DeclareMathOperator{\ZPP}{\mathbf{ZPP}}
\DeclareMathOperator{\RP}{\mathbf{RP}}
\DeclareMathOperator{\coRP}{\mathbf{coRP}}
\DeclareMathOperator{\BPL}{\mathbf{BPL}}
\DeclareMathOperator{\IP}{\mathbf{IP}}
\DeclareMathOperator{\PSPACE}{\mathbf{PSPACE}}
\DeclareMathOperator{\NPSPACE}{\mathbf{NPSPACE}}
\DeclareMathOperator{\SAT}{\mathsf{SAT}}
\DeclareMathOperator{\NL}{\mathbf{NL}}
\DeclareMathOperator{\PCP}{\mathbf{PCP}}
\DeclareMathOperator{\PP}{\mathbf{PP}}
\DeclareMathOperator{\cost}{cost}
\let\Pr\relax
\DeclareMathOperator*{\Pr}{\mathbf{Pr}}

\definecolor{shadecolor}{gray}{0.9}

\theoremstyle{plain}
\newtheorem*{lem}{Lemma}

\theoremstyle{plain}
\newtheorem*{claim}{Claim}

\theoremstyle{definition}
\newtheorem*{answer}{Answer}

\newtheorem{theorem}{Theorem}[section]
\newtheorem*{thm}{Theorem}
\newtheorem{corollary}{Corollary}[theorem]
\newtheorem{lemma}[theorem]{Lemma}

\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\footrulewidth}{0.4pt}

\setlength{\parindent}{0pt}

\pagestyle{fancy}

\renewcommand{\thefootnote}{\fnsymbol{footnote}}

% start MZ
\usetikzlibrary{automata,positioning}
\let\oldemptyset\emptyset
\renewcommand{\emptyset}{\text{\O}}
\renewcommand\qedsymbol{$\blacksquare$}
\newenvironment{prf}{{\bfseries Proof.}}{\qedsymbol}
\renewcommand{\emph}[1]{\textit{\textbf{#1}}}
\newcommand{\annotate}[1]{\textit{\textcolor{blue}{#1}}}
\usepackage{stmaryrd}
\usepackage{minted}
\usepackage{mathtools}
\usepackage{alltt}
\newcommand{\ttt}[1]{\texttt{#1}}
\newcommand{\match}[1]{\textbf{\underline{#1}}}
% end MZ

\begin{document}

\maketitle

\textbf{All questions due Friday, August 2nd at 3:00PM.} \\

This fifth problem set explores the regular languages and their properties. This will be your first
foray into computability theory, and I hope you find it fun and exciting! \\

Note that some of the questions will require you to submit an automata or regular expression you create
via our online editors. Please follow the instructions in the handout to access these tools and submit your work. 
There is no need to copy your constructions back into this written submission as we will look only at your
online submission for grading these questions. \\ 

As always, please feel free to drop by office hours, ask on Piazza, or email the staff list if you have
any questions. We'd be happy to help out. \\

Good luck, and have fun! 
\pagebreak

\section{Constructing DFAs}

For each of the following languages over the indicated alphabets, construct a DFA that accepts precisely the strings that are in the indicated language. Your DFA does not have to have the fewest number of states possible, though for your own edification we'd recommend trying to construct the smallest DFAs possible. \\

\emph{Please use our online tool to design, test, and submit your answers to this problem. Handwritten or typed solutions will not be accepted.} To use the tool, visit the CS103 website and click the ``DFA/NFA Editor'' link under the ``Resources'' header. If you submit in a pair, in your GradeScope submission, let us know the SUNetID (e.g. htiek, but not 06001234) of the partner who submitted the DFAs. \\

Unlike the programming assignments, you will not be able to see the results of the autograder when you submit. As a result, \emph{be sure to test your solutions thoroughly before you submit!}

\begin{enumerate}[label*=\roman*.,ref=\roman*]
    \item 
    \begin{minipage}[t]{.55\textwidth}
    There are many ways to tile a $2 \times 8$ checkerboard with dominoes, two of which are shown to the right. Notice that the horizontal dominoes must appear as stacked pairs (do you see why?) We can read each tiling from left to right as a string made from the characters \ttt{I} and \ttt{B}, where \ttt{I} denotes ``a vertical domino'' and \ttt{B} denotes ``two horizontal dominoes.'' The top tiling here would be represented as \ttt{BIBIII} and the bottom tiling as \ttt{IBBBI}.
    \end{minipage}
    \quad
    \begin{minipage}[t]{.4\textwidth}
    \tikzset{
        rect white/.style={draw, fill=white},
        rect gray/.style={draw, fill=black!20},
        rect blue/.style={draw=none, fill=blue!40},
    }
    \begin{tikzpicture}[scale=0.7,baseline={(current bounding box.north)}]
        \draw[rect white] (0,0) rectangle (1,1);
        \draw[rect gray] (1,0) rectangle (2,1);
        \draw[rect white] (2,0) rectangle (3,1);
        \draw[rect gray] (3,0) rectangle (4,1);
        \draw[rect white] (4,0) rectangle (5,1);
        \draw[rect gray] (5,0) rectangle (6,1);
        \draw[rect white] (6,0) rectangle (7,1);
        \draw[rect gray] (7,0) rectangle (8,1);
        \draw[rect gray] (0,1) rectangle (1,2);
        \draw[rect white] (1,1) rectangle (2,2);
        \draw[rect gray] (2,1) rectangle (3,2);
        \draw[rect white] (3,1) rectangle (4,2);
        \draw[rect gray] (4,1) rectangle (5,2);
        \draw[rect white] (5,1) rectangle (6,2);
        \draw[rect gray] (6,1) rectangle (7,2);
        \draw[rect white] (7,1) rectangle (8,2);
        \draw[rect blue] (0.1,0.1) rectangle (1.9,0.9);
        \draw[rect blue] (0.1,1.1) rectangle (1.9,1.9);
        \draw[rect blue] (2.1,0.1) rectangle (2.9,1.9);
        \draw[rect blue] (3.1,0.1) rectangle (4.9,0.9);
        \draw[rect blue] (3.1,1.1) rectangle (4.9,1.9);
        \draw[rect blue] (5.1,0.1) rectangle (5.9,1.9);
        \draw[rect blue] (6.1,0.1) rectangle (6.9,1.9);
        \draw[rect blue] (7.1,0.1) rectangle (7.9,1.9);
    \end{tikzpicture} \\
    
    \begin{tikzpicture}[scale=0.7,baseline={(current bounding box.north)}]
        \draw[rect white] (0,0) rectangle (1,1);
        \draw[rect gray] (1,0) rectangle (2,1);
        \draw[rect white] (2,0) rectangle (3,1);
        \draw[rect gray] (3,0) rectangle (4,1);
        \draw[rect white] (4,0) rectangle (5,1);
        \draw[rect gray] (5,0) rectangle (6,1);
        \draw[rect white] (6,0) rectangle (7,1);
        \draw[rect gray] (7,0) rectangle (8,1);
        \draw[rect gray] (0,1) rectangle (1,2);
        \draw[rect white] (1,1) rectangle (2,2);
        \draw[rect gray] (2,1) rectangle (3,2);
        \draw[rect white] (3,1) rectangle (4,2);
        \draw[rect gray] (4,1) rectangle (5,2);
        \draw[rect white] (5,1) rectangle (6,2);
        \draw[rect gray] (6,1) rectangle (7,2);
        \draw[rect white] (7,1) rectangle (8,2);
        \draw[rect blue] (0.1,0.1) rectangle (0.9,1.9);
        \draw[rect blue] (1.1,0.1) rectangle (2.9,0.9);
        \draw[rect blue] (1.1,1.1) rectangle (2.9,1.9);
        \draw[rect blue] (3.1,0.1) rectangle (4.9,0.9);
        \draw[rect blue] (3.1,1.1) rectangle (4.9,1.9);
        \draw[rect blue] (5.1,0.1) rectangle (6.9,0.9);
        \draw[rect blue] (5.1,1.1) rectangle (6.9,1.9);
        \draw[rect blue] (7.1,0.1) rectangle (7.9,1.9);
    \end{tikzpicture}
    \end{minipage}

    Let $\Sigma$ be the alphabet $\{\ttt{B}, \ttt{I}\}$. Construct a DFA for the language $\{ w \in \Sigma^* \mid w$ represents a domino tiling of a $2 \times 8$ checkerboard\}.
    
    \item You're taking a walk with your dog along a straight-line path. Your dog is on a leash of length two, so the distance between you and your dog can be at most two units. You and your dog start at the same position. Consider the alphabet $\Sigma = \{\ttt{y}, \ttt{d}\}$. A string in $\Sigma^*$ can be thought of as a series of events in which either you or your dog moves forward one unit. For example, the string \ttt{yydd} means you take two steps forward, then your dog takes two steps forward.
    
    Let $L$ be the language $\{ w \in \Sigma^* \mid w$ describes a series of steps where you and your dog are never more than two units apart\}. Construct a DFA for $L$.
    
    \item Let $\Sigma = \{\ttt{a}, \ttt{b}, \ttt{c}, \ldots, \ttt{z}\}$. Construct a DFA for the language $\{ w \in \Sigma^*\ |\ w$ contains the word \ttt{cocoa} as a substring\}. For example, $\ttt{mm\match{cocoa}mm} \in L$ and $\ttt{\match{cocoa}} \in L$, but $\ttt{c} \notin L$, $\ttt{chocolate} \notin L$ (though \ttt{cocoa} is a sub\emph{sequence} of \ttt{\match{c}h\match{oco}l\match{a}te}. it's not a sub\emph{string}), and $\epsilon \notin L$
    
    Fun fact: DFAs and their variants are often used in string-processing algorithms and data structures. Take CS166 for more details!

    \annotate{Test your automaton thoroughly. This one has some tricky edge cases.}

\end{enumerate}

\begin{shaded}
Write the SUNetID of the person who submitted the DFAs here. 
\end{shaded}

\pagebreak

\section{Constructing NFAs}

For each of the following languages over the indicated alphabets, construct an NFA that accepts precisely the strings that are in the indicated language. \emph{Please use our online system to design, test, and submit your automata}; see above for details. As before, \emph{please test your submissions thoroughly!}

As before, while you don't have to submit the smallest NFAs possible, we recommend that you try to keep your NFAs small both to make testing easier and for your own edification.

\begin{enumerate}[label*=\roman*.,ref=\roman*]
    \item For the alphabet $\Sigma = \{\ttt{a}, \ttt{b}, \ttt{c}\}$, construct an NFA for the language $\{ w \in \Sigma^* \mid w$ ends in \ttt{a}, \ttt{bb}, or \ttt{ccc} \}.
    
    \annotate{While it's possible to do this completely deterministically, it's a bit easier if you use the ``guess-and-check'' framework we talked about in class.}

    \item For the alphabet $\Sigma = \{\ttt{a}, \ttt{b}, \ttt{c}, \ttt{d}, \ttt{e}\}$, construct an NFA for the language $\{ w \in \Sigma^*\ |$ the last character of $w$ appears nowhere else in $w$, and $|w| \ge 1 \}$. 
    
    \annotate{This problem is all about embracing nondeterminism. Use the ``guess-and-check'' framework. What information would you want to guess? How would you check it? Please don't try to solve this problem by building a DFA for this language; you'll need at least 50 states if you try to approach things this way.}
    
    \annotate{Stuck? Try reducing the alphabet to two or three letters and see if you can solve that version.}

    \item For the alphabet $\Sigma = \{\ttt{a}, \ttt{b}\}$, construct an NFA for the language $\{w \in \Sigma^* \mid w$ contains at least two \ttt{b}'s with exactly five characters between them\}. For example, \ttt{\underline{b}aaaaa\underline{b}} is in the language, as is \ttt{aabaa\underline{b}aaabb\underline{b}} and \ttt{a\underline{b}bbbba\underline{b}aaaaaaab}, but \ttt{bbbbb} is not, nor are \ttt{bbbab} or \ttt{aaabab}.
    
    \annotate{The smallest DFA for this language is pretty big, so please don't solve this one deterministically. Embrace the nondeterminism! What would you like to guess? How would you check that your guess is right?}

\end{enumerate}

\begin{shaded}
Write the SUNetID of the person who submitted the NFAs here. 
\end{shaded}

\pagebreak

\section{Designing Regular Expressions}

Below are a list of alphabets and languages over those alphabets. For each language, write a regular expression for that language. \emph{Please use our online tool to design, test, and submit your regular expressions. Typed or handwritten solutions will not be accepted.} To use it, visit the CS103 website and click the ``Regex Editor'' link under the ``Resources'' header. If you submit in a pair, please tell us in your GradeScope submission who submitted your answers to this question. Also, as a reminder, please test your submissions thoroughly, since we'll be grading them with an autograder.

\begin{enumerate}[label*=\roman*.,ref=\roman*]
    \item Let $\Sigma = \{\ttt{a}, \ttt{b}, \ttt{c}, \ttt{d}, \ttt{e}\}$. Write a regular expression for the language $\{w \in \Sigma^* \mid $ the letters in $w$ are sorted alphabetically\}. 
    
    \annotate{Note that strings in this language could be just a single character such as \ttt{a}, \ttt{b}, \ttt{c}, and could also contain repeated letters such as \ttt{aaaabbbcc}.}
    
    \item Write a regular expression for the complement of the language from part (i) of this problem.
    
    \annotate{As with NFAs, there's no simple way to start with a regex for a language $L$ and to turn it into a regex for $\overline{L}$.}
    
    \item On Unix-style operating systems like macOS or Linux, files are organized into directories. You can reference a file by giving a \textit{path} to the file, a series of directory names separated by slashes. For example, the path \ttt{/home/username/} might represent a user's home directory, and a path like \ttt{/home/username/Documents/PS5.tex} might represent that person's solution to this problem set. Paths that start with a slash character are called \textit{absolute paths} and say exactly where the file is on disk. Paths that don't start with a slash are called \textit{relative paths} and say where, relative to the current folder, a file can be found. For example, if I'm logged into my computer and am in my home folder, I could look up the file \ttt{Documents/PS5.tex} to find my solution to this problem set.
    
    The general pattern here is that a file path consists of a series of directory or file names separated by slashes. That path might optionally start with a slash, but isn't required to, and it might option- ally end with a slash, but isn't required to. However, you can't have two consecutive slashes. \footnote{In some cases you technically \textit{can} have multiple consecutive slashes, but we'll ignore that for now.}
    
    Let $\Sigma = \{a,/\}$. Write a regular expression for $L = \{w \in \Sigma^* \mid w$ represents the name of a file path on a Unix-style system \}. For example, $\ttt{/aaa/a/aa} \in L$, $\ttt{/} \in L$, $\ttt{a} \in L$, $\ttt{/a/a/a/} \in L$, and $\ttt{aaa/} \in L$, but $\ttt{//a//} \notin L$, $\ttt{a//a} \notin L$, and $\varepsilon \notin L$.
    
    Fun fact: this problem comes from my job, where I fixed a bug in industrial code that arose when someone wrote the wrong regex for this language. 
    
    \item Suppose you are taking a walk with your dog on a leash of length two. Let $\Sigma = \{\ttt{y}, \ttt{d}\}$ and let  $L = \{w \in \Sigma^* \mid w$ represents a walk with your dog on a leash where you and your dog both end up at the same location\}. For example, we have $\ttt{yyddddyy} \in L$ because you and your dog are never more than two steps apart and both of you end up four steps ahead of where you started; similarly, $\ttt{ddydyy} \in L$. However, $\ttt{yyyyddd} \notin L$, since halfway through your walk you're three steps ahead of your dog; $\ttt{ddyd} \notin L$, because your dog ends up two steps ahead of you; and $\ttt{ddyddyyy} \notin L$, because at one point your dog is three steps ahead of you. Write a regular expression for $L$.
    
    \annotate{Note that, unlike in Problem 1, you and your dog \textbf{must} end at the same position.}
    
\end{enumerate}
\begin{shaded}
Write the SUNetID of the person who submitted the regular expressions here. 
\end{shaded}

\pagebreak

\section{Finite Languages}

A language $L$ is called \emph{finite} if $L$ contains finitely many strings (that is, $|L|$ is a natural number). \\

Given a finite language $L$, explain how to write a regular expression for $L$. Briefly justify your answer; no formal proof is necessary. This shows that all finite languages are regular. \\
    
\annotate{Watch for edge cases!}
    
\begin{shaded}
Write your answer here.
\end{shaded}

\section{Complementing NFAs}

In lecture, we saw that if you take a DFA for a language $L$ and flip all the accepting and rejecting states, you end up with a DFA for $\overline{L}$. \\

\begin{enumerate}[label=\roman*.]
    \item Draw a simple NFA for a language $L$ where flipping all the accepting and rejecting states does \emph{not} produce an NFA for $\overline{L}$. Briefly justify your answer; you should need at most a sentence or two.

    \begin{shaded}
    Write your answer and justification here. 
    \end{shaded}

    \item Explain why your result from part (i) doesn't contradict the fact that the regular languages are closed under complementation.
    
    \begin{shaded}
    Write your answer here.
    \end{shaded}
\end{enumerate}

\pagebreak 

\section{Monoids and Kleene Stars}

The Kleene star operator is one of the more unusual operators we've covered over the course of the quarter. This problem explores one of its fundamental properties. \\

Let $\Sigma$ be an arbitrary alphabet. A \emph{monoid over $\mathbf{\Sigma}$} is a set $M \subseteq \Sigma^*$ with the following properties:
\begin{equation*}
\varepsilon \in M \quad\quad\quad \forall x \in M.\ \forall y \in M.\ xy \in M.
\end{equation*}

Let $L$ be an arbitrary language over $\Sigma$ and let $M$ be an arbitrary monoid over $\Sigma$. Prove by induction that if $L \subseteq M$, then $L^* \subseteq M$. In the course of writing this proof, please call back to the formal definition of language concatenation and the Kleene star. Here's a refresher on the definitions:
    \begin{align*}
    L_1L_2 &= \{ wx\ |\ w \in L_1\text{ and }x \in L_2 \} \\
    L^0 &= \{\varepsilon\} \quad\quad\quad L^{n+1} = LL^n \\
    L^* &= \{ w\ |\ \exists n \in \N.\ w \in L^n \}
    \end{align*}
    
\annotate{To get yourself acquainted with monoids, try giving three examples of monoids. At least one of them
should be finite, and at least one of them should be infinite.} \\

\annotate{This problem is all about finding the right way to formalize things. Think about, ultimately, what it is that
you need to prove. Before you start trying to prove that, break the task down into smaller pieces and make
sure you organize everything in a way that makes the logical flow easy to read and rigorously covers all
cases. Once you have the setup put together, dive in and fill out each section.} \\
    
\annotate{If you'd like to use any properties of Kleene stars, language concatenation, etc. that aren't given in the definition, you'll need to prove them first.} \\

\begin{shaded}
Provide a proof here. 
\end{shaded}

The result that you've shown here is a building block toward a larger result: If $L$ is a language over $\Sigma$, then $L^*$ is the smallest monoid over $\Sigma$ that contains $L$.
This is a very different way of thinking about the Kleene star. Rather than talking about $L^*$ in terms of powers of languages, we can think of $L^*$ as ``what set do you get if you start with $L$ and add as little as possible to make it contain $\epsilon$ and be closed under concatenation?'' That's quite a departure from where we started! \\

The monoids we explored in this problem are actually a special case of a broader class of objects (what we've been calling ``monoids'' are actually ``concatenative monoids,'' since they focus on string concatenation). The more general version of monoids shows up in parallel programming (most famously, in MapReduce) as a way of describing what sorts of computational jobs can be split apart and joined back together later on, as well as in programming language theory as a way of capturing the notion of ``computation with side effects.'' 

\newpage
\section{Concatenation, Kleene Stars, and Complements}

The regular languages are closed under a number of different operations. This problem explores some
properties of those operations. \\

We've talked about \emph{cardinality} of a set as the number of elements it
contains. In our very first lecture, we saw that we can look at cardinality as a \textit{relation}
between two sets rather than an absolute quantity. More formally, let's now formally define what it means for two sets to have the same cardinality:
\begin{center}
$|S| = |T|$ if there exists a bijection $f : S \rightarrow T$.
\end{center}

\begin{enumerate}[label*=\roman*.,ref=\roman*]
    \item Prove or disprove: if $L$ is a nonempty, finite language and $k$ is a positive natural number, then $|L^k| = |L|^k$. Here, the notation  $|L|^k$ represents ``the cardinality of $L$, raised to the $k$th power,'' and the notation $|L^k|$ represents ``the cardinality of the $k$-fold concatenation of $L$ with itself.''
    
    \annotate{Call back to formal definitions as you work through this problem, and proceed slowly and carefully. This one is subtle. Write out what you would need to show in order to prove this statement and what you would need to show in order to disprove this statement, then explore both branches.}
    
    \begin{shaded}
    Provide a proof or disproof here. 
    \end{shaded}
    
    \item Prove or disprove: there is a language $L$ where $\overline{(L^*)} = (\overline{L})^*$.
    
    \annotate{A good warm-up problem: what is $\varnothing^*$? Don't answer this question based off of your intuition; look back at the formal definition of the Kleene star.}
    
    \begin{shaded}
    Provide a proof or disproof here. 
    \end{shaded}
\end{enumerate}

\pagebreak 

\section{DFAs, Formally}
When we first talked about graphs, we saw them first as pictures (objects connected by lines), then formally defined a graph $G$ as an ordered pair $(V, E)$, where $V$ is a set of nodes and $E$ is a set of edges. This rigorous definition tells us what a graph actually is in a mathematical sense, rather than just what it looks like. \\

We've been talking about DFAs for a while now and seen how to draw them both as a collection of states with transitions (that is, as a state-transition diagram) and as a table with rows for states and columns for characters. But what exactly \textit{is} a DFA, in a mathematical sense? \\

Formally speaking, a DFA is a 5-tuple $(Q, \Sigma, \delta, q_0, F)$, where
\begin{itemize}
    \item $Q$ is a finite set, the elements of which we call \textit{states};
    \item $\Sigma$ is a finite, nonempty set, the elements of which we call \textit{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 accepting states.
\end{itemize}
The transition function warrants a bit of explanation. When we've drawn DFAs, we've represented the transitions either by arrows labeled with characters or as a table with rows and columns corresponding to states and symbols, respectively. In this formal definition, the transition function $\delta$ is what ultimately specifies the transition (the $\delta$ symbol is a Greek lower-case delta). \\

First, let's talk about the domain and codomain of this function. We're introducing some new notation when we say the domain of this function is $Q \times \Sigma$. If $A$ and $B$ are sets, the \textbf{\textit{Cartesian product}} of $A$ and $B$, denoted $\mathbf{A \times B}$,
is the set
\begin{equation*}
\{ (x, y)\ |\ x \in A \land y \in B \}
\end{equation*}
Intuitively, $A \times B$ is the set of all ordered pairs you can make by taking one element from $A$ and one element
from $B$, in that order. For example, the set $\{\textcolor{red}{1}, \textcolor{red}{2}\} \times \{\textcolor{blue}{u}, \textcolor{blue}{v}, \textcolor{blue}{w}\}$ is
\begin{equation*}
\{\ (\textcolor{red}{1}, \textcolor{blue}{u}), (\textcolor{red}{1}, \textcolor{blue}{v}), (\textcolor{red}{1}, \textcolor{blue}{w}), (\textcolor{red}{2}, \textcolor{blue}{u}), (\textcolor{red}{2}, \textcolor{blue}{v}), (\textcolor{red}{2}, \textcolor{blue}{w})\ \}
\end{equation*}

Thus, the input to our function will be an ordered pair of the form $(q, a)$ where $q \in Q$ and $a \in \Sigma$. Then the transition from state $q$ on symbol $a$ is given by $\delta(q, a)$, which produces an element in our codomain $Q$ representing the state we should transition to from $q$ upon reading $a$. \\

This question explores some properties of this rigorous definition.

\begin{enumerate}[label*=\roman*.,ref=\roman*]
    \item Is it possible for a DFA to have no states? If so, define a DFA with no states as a 5-tuple, explaining why your 5-tuple meets the above requirements. If not, explain why not.
    
    \annotate{To define an object using a 5-tuple, use this template: ``Let $D = (Q, \Sigma, \delta, q_0, F)$, where $Q = \dots, \Sigma = \dots$,'' etc. Defining a DFA requires you to define a transition function $\delta$. To help you see how our study of functions this quarter applies here, we'd like you to formally define $\delta$ either using a fixed rule or as a piecewise function. For the purposes of this problem, please \textbf{do not} give a picture or table for $\delta$, even though in general these could be valid ways of describing a function. If you've having trouble doing so, it might mean that you picked too complex of a DFA and might want to search for something simpler.}
    
    \begin{shaded}
    Write your answer here.
    \end{shaded}
    
    \item Is it possible for a DFA to have no \textit{accepting} states? If so, define a DFA with no accepting states as a 5-tuple, explaining why your 5-tuple meets the above requirements. If not, explain why not.
    
    \begin{shaded}
    Write your answer here.
    \end{shaded}
    
    \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 above definition guarantees this?
    
    \begin{shaded}
    Write your answer here.
    \end{shaded}
    
    \item Is it possible for a DFA to have an unreachable state (that is, 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, explaining why your 5-tuple meets the above requirements. If not, explain why not.
    
    \begin{shaded}
    Write your answer here.
    \end{shaded}
\end{enumerate}

\pagebreak 

We've included several optional fun problems here. Feel free to work on any number of them, but please submit at most one of them with your problem set. If you submit more than one problem, we'll select which one to grade arbitrarily and capriciously. \smiley

\section*{Optional Fun Problem One: Why Finite? (Extra Credit)}

We'll say that a \emph{deterministic infinite automaton}, or \emph{DIA}, is a generalization of a DFA in which the automaton has infinitely many different states. Formally speaking, a DIA is given by the same 5-tuple definition as a DFA from Problem Nine, except that $Q$ must be an infinite set. Since DIAs have infinitely many states, ther're mostly an object of purely theoretical study. You couldn't actually build one in the real world. \\

Prove that if $L$ is an arbitrary language over an alphabet $\Sigma$, then there is a DIA that accepts $L$ (that is, the DIA accepts every string in $L$ and rejects every string not in $L$.) To do so, show how to start with a language $L$, formally define a 5-tuple corresponding to a DIA for $L$, then formally prove that that DIA accepts all and only the strings in $L$.

\begin{shaded}
Write your answer and proof here. 
\end{shaded}

\section*{Optional Fun Problem Two: Edit Distances (Extra Credit)}

The \emph{edit distance} between two strings $w$ and $x$ is the minimum number of edits that need to be made to $w$ to convert it into $x$. Here, an \emph{edit} consists of either adding a character somewhere into $w$, deleting a character
somewhere from $w$, or replacing a character of $w$ with another. For example, \ttt{cat} and \ttt{dog} have edit
distance 3, \ttt{table} and \ttt{maple} have edit distance 2, and \ttt{edit} and \ttt{distance} have edit distance 6. \\

Let $\Sigma = \{\ttt{w}, \ttt{h}, \ttt{i}, \ttt{m}, \ttt{s}, \ttt{y}\}$. Design an NFA for $\{w \in \Sigma^* \mid$ the edit distance of $w$ and \ttt{whimsy} is at most
three\}. Submit your answer online, and let us know in your written assignment who made the submission.

\begin{shaded}
Write the SUNetID of the person who submitted the NFA here. 
\end{shaded}
\end{document}
