%
% 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.
%
\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{Sachin Padmanabhan}
\date{\today}
\lhead{Sachin Padmanabhan}
\chead{Problem Set \#6}
\rhead{\today}
\lfoot{}
\cfoot{CS 103: Mathematical Foundations of Computing --- Fall 2017}
\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}}
\begin{document}
\maketitle
\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 weed recommend trying to construct the smallest DFAs possible. \\
\textit{\textbf{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're planning on submitting this assignment in a pair, in
your GradeScope submission, please let us know the SUNetID (e.g. htiek, fidels) of the partner who submitted
the DFAs so that we can match the problem set to the submitted answers. \\
Unlike the programming assignments, you will not be able to see the results of the autograder when you
submit. As a result, \textit{\textbf{be sure to test your solutions thoroughly before you submit!}}
\begin{enumerate}[label*=\roman*.,ref=\roman*]
\item For the alphabet $\Sigma = \{a, b, c\}$, construct a DFA for the language $\{ w \in \Sigma^*\ |\ w$ contains exactly
two $c$s.$\}$
\item For the alphabet $\Sigma = \{a, b\}$, construct a DFA for the language $\{ w \in \Sigma^*\ |\ w$ contains the same
number of instances of the substring $ab$ and the substring $ba\}$. Note that substrings are allowed
to overlap, so $aba \in L$ and $babab \in L$.
\item For the alphabet $\Sigma = \{a, b, c, \ldots, z\}$, construct a DFA for the language $\{ w \in \Sigma^*\ |\ w$ contains the
word ``$cocoa$'' as a substring$\}$. \footnote{DFAs are often used to search large blocks of text for specific substrings, and several string searching algorithms are built on top of specially-constructed DFAs. The \textit{Knuth-Morris-Pratt} and \textit{Aho-Corasick} algorithms use slightly modified DFAs to find substrings extremely efficiently.}
\item Suppose that you are taking a walk with your dog along a straight-line path. Your dog is on a
leash that has length two, meaning that 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 = \{y, 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 ``$yydd$'' means that you take two steps forward, then your dog takes
two steps forward. Let $L = \{ w \in \Sigma^*\ |\ w$ describes a series of steps that ensures that you and your
dog are never more than two units apart$\}$. Construct a DFA for $L$.
\end{enumerate}
\begin{shaded}
Write the SUNetID of the person who submitted the DFAs here.
\end{shaded}
\newpage
\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. \textit{\textbf{Please use our online system to design, test, and submit
your automata}}; see above for details. As before, \textit{\textbf{please test your submissions thoroughly!}}
\begin{enumerate}[label*=\roman*.,ref=\roman*]
\item For the alphabet $\Sigma = \{a, b, c\}$, construct an NFA for the language $\{ w \in \Sigma^*\ |\ w$ ends in $a$, $bb$, or
$ccc \}$.
\item For the alphabet $\Sigma = \{a, b, c, d, e\}$, construct an NFA for the language $\{ w \in \Sigma^*\ |$ the last character
of $w$ appears nowhere else in $w$, and $|w| \ge 1 \}$.
\item For the alphabet $\Sigma = \{a, b\}$, construct an NFA for the language $\{ w \in \Sigma^*\ |\ w$ contains at least two
$b$'s with exactly five characters between them$\}$. For example, $\underline{b}aaaaa\underline{b}$ is in the language, as is
$aabaa\underline{b}aaabb\underline{b}$ and $a\underline{b}bbbba\underline{b}aaaaaaab$, but $bbbbb$ is not, nor are $bbbab$ or $aaabab$.
\end{enumerate}
\begin{shaded}
Write the SUNetID of the person who submitted the NFAs here.
\end{shaded}
\section{ $\wp(\Sigma^*)$}
Let $\Sigma$ be an alphabet. Give a short English description of the set $\wp(\Sigma^*)$. Briefly justify your answer. \textit{(We
think that there is a single ``best answer.'' You should be able to describe the set in at most ten words)}
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
Provide justification here.
\end{shaded}
\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.
\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.''
\begin{shaded}
Provide a proof or disproof here.
\end{shaded}
\item Prove or disprove: there is a language $L$ where $\overline{(L^*)} = \overline{(L)}^{\ *}$.
\begin{shaded}
Provide a proof or disproof here.
\end{shaded}
\end{enumerate}
\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 \textit{\textbf{monoid over $\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 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, and use induction as appropriate. 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*}
\begin{shaded}
Provide a proof here.
\end{shaded}
The result that you've shown here is a building block toward a larger result: the Kleene star of a language
$L$ is the smallest monoid containing all the strings in $L$.
\newpage
\section{Hard Reset Sequences}
A \textit{\textbf{hard reset sequence}} for a DFA is a string $w$ with the following property: starting from any state in the
DFA, if you read $w$, you end up in the DFA's start state. \\
Hard reset sequences have many practical applications. For example, suppose you're remotely controlling
a Mars rover whose state you're modeling as a DFA. Imagine there's a hardware glitch that puts the Mars
rover into a valid but unknown state. Since you can't physically go to Mars to pick up the rover and fix it,
the only way to change the rover's state would be to issue it new commands. To recover from this mishap,
you could send the rover a hard reset sequence. Regardless of what state the rover got into, this procedure
would guarantee that it would end up in its initial configuration. \\
Here is an algorithm that, given any DFA, will let you find every hard reset sequence for that DFA:
\begin{enumerate}
\item Add a new start state $q_s$ to the automaton with $\varepsilon$-transitions to every state in the DFA.
\item Perform the subset construction on the resulting NFA to produce a new DFA called the \textit{\textbf{power automaton}}.
\item If the power automaton contains a state corresponding solely to the original DFA's start state,
make that state the only accepting state in the power automaton. Otherwise, make every state in
the power automaton a rejecting state.
\end{enumerate}
This process produces a new automaton that accepts all the hard reset sequences of the original DFA. It's
possible that a DFA won't have any hard reset sequences (for example, if it contains a dead state), in
which case the new DFA won't accept anything. \\
Apply the above algorithm to the following DFA and give us a hard reset sequence for that DFA. For simplicity,
please give the subset-constructed DFA as a transition table rather than a state-transition diagram.
We've given you space for the table over to the right, and to be nice, we've given you exactly the number
of rows you'll need.
\begin{shaded}
\begin{answer}
$ $ \\
\begin{tikzpicture}[shorten >=1pt,node distance=2.5cm,on grid,auto]
% \node[state, options?] (identifier) [placement] {display};
\node[state] (2) {$q_2$};
\node[state, initial] (0) [above left=of 2] {$q_0$};
\node[state] (1) [above right=of 2] {$q_1$};
\path[->]
(0) edge node {$\Sigma$} (1)
(1) edge node {$b$} (2)
edge [loop right] node {$a$} (1)
(2) edge node {$b$} (0)
edge [loop below] node {$a$} (2);
\end{tikzpicture}
\begin{tabularx}{9cm}{|C|C|C|}
\hline
\diagbox[dir=SW, width=3cm] & $a$ & $b$ \\
\hline
% TODO: fill in table entries (hlines show horizontal dividers, ampersands show vertical column dividers)
(sample) & (sample) & (sample) \\
\hline
& & \\
\hline
& & \\
\hline
& & \\
\hline
& & \\
\hline
& & \\
\hline
& & \\
\hline
& & \\
\hline
\end{tabularx}
\bigskip
\begin{center}
Sample hard reset sequence: \underline{Write your answer here.}
\end{center}
\end{answer}
\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}$. \\
Draw a simple NFA for a language $L$ where flipping all the accepting and rejecting states does not produce
an NFA for $\overline{L}$. Briefly justify your answer; you should need at most a sentence or two here.
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
Provide justification here.
\end{shaded}
\section{DFAs, Formally}
When we first talked about graphs, we saw them first as pictures (objects connected by lines, but 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 diagrams 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 \textit{\textbf{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. Specifically, for any state $q \in Q$ and any symbol $a \in \Sigma$, the transition from state $q$ on
symbol $a$ is given by $\delta(q, 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.
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\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}
\begin{answer}
Write your answer here.
\end{answer}
\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}
\begin{answer}
Write your answer here.
\end{answer}
\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}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\end{enumerate}
Going forward, in CS103, we won't use the formal definition of DFAs in our proofs, not because it's not
useful, but because it often makes the reasoning a bit harder to follow. However, we thought you should at
least see the definition, since it's useful for formalizing what a DFA actually is!
\section{Why the Extra State?}
In our proof that the regular languages are closed under the Kleene closure operator (that is, if $L$ is regular,
then $L^*$ is regular), we used the following construction:
\begin{enumerate}
\item Begin with an NFA $N$ where $\mathscr{L}(N) = L$.
\item Add in a new start state $q_{start}$.
\item Add an $\varepsilon$-transition from $q_{start}$ to the start state of $N$.
\item Add $\varepsilon$-transitions from each accepting state of $N$ to $q_{start}$.
\item Make $q_{start}$ an accepting state.
\item Make every state besides $q_{start}$ a rejecting state.
\end{enumerate}
You might have wondered why we needed to add $q_{start}$ as a new state to the NFA. It might have seemed
more natural to do the following:
\begin{enumerate}
\item Begin with an NFA $N$ where $\mathscr{L}(N) = L$.
\item Add $\varepsilon$-transitions from each accepting state of $N$ to the start state of $N$.
\item Make the start state of $N$ an accepting state.
\item Make every state of $N$ a rejecting state.
\end{enumerate}
Unfortunately, this construction does not work correctly. \\
Find a regular language $L$ and an NFA $N$ for $L$ such that using the second construction does not create an
NFA for $L^*$. Justify why the language of the new NFA isn't $L^*$.
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
Provide justification here.
\end{shaded}
\section{Optional Fun Problem: Why Finite? (1 Point Extra Credit)}
The term ``finite'' in finite automata refers to the fact that each automaton can only have finitely many
states. It turns out there's a good reason for that. \\
We'll say that a \textit{\textbf{deterministic infinite automaton}}, or \textit{\textbf{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 Eight, except that $Q$ must be an infinite set. Since DIAs have infinitely many
states, they can't actually be built, and so are mostly an object of purely theoretical study. \\
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}
\begin{answer}
Write your answer here.
\end{answer}
Provide a proof here.
\end{shaded}
\end{document}