% % 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 Fall 2018 by Michael Zhu \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 \#6} \author{Your Name(s) Here} \date{\today} \lhead{Your Name(s) Here} \chead{Problem Set \#6} \rhead{\today} \lfoot{} \cfoot{CS 103: Mathematical Foundations of Computing --- Winter 2020} \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 \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 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 $\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.} \item You can approximate the number of syllables in an English word by counting up the number of vowels in the word (including y), \textit{except} for \begin{itemize} \item vowels that have vowels directly before them, and \item the letter \ttt{e}, if it appears by itself at the end of a word. \end{itemize} For example, the word \ttt{pr\match{o}gr\match{a}m} has two syllables; the word \ttt{p\match{ea}ch} has one syllable; the word \ttt{d\match{e}d\match{u}ce} has two syllables, since the final \ttt{e} does not count as a syllable; the word \ttt{\match{o}b\match{oe}} has two syllables (although it ends in an \ttt{e}, that \ttt{e} is preceded by another vowel); the word \ttt{wh\match{y}} has one syllable, since \ttt{y} counts as a vowel; and the word \ttt{\match{e}nq\match{ueue}} has two syllables. This approach isn't always correct -- it will say that \ttt{\match{a}r\match{ea}} has two syllables -- but it's still a good approximation. Let $\Sigma = \{\ttt{a}, \ttt{b}, \ttt{c}, ..., \ttt{z}\}$. Construct a DFA for the language $\{w \in \Sigma^* \mid w$ has at least two syllables according to the above heuristic\}. \annotate{The strings in this language don't necessarily have to be English words. For example, it contains the nonsense string \ttt{w\match{e}kr\match{u}vbsdf}.} \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 Let $\Sigma = \{\ttt{a}, \ttt{b}, \ttt{c}, \ttt{d}, \ttt{e}\}$. Construct an NFA for the language $L = \{ w \in \Sigma^* \mid$ the letters in $w$ are sorted alphabetically\}. For example, $\ttt{abcde} \in L, \ttt{bee} \in L$, and $\epsilon \in L$, but $\ttt{decade} \notin L$. \annotate{You could do this deterministically, but that will require a \textbf{lot} of transitions. You can dramatically reduce that number by using $\epsilon$-transitions strategically.} \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{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*} \begin{enumerate}[label=\roman*.] \item 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. 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. One 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} \end{enumerate} \pagebreak \section{Hard Reset Sequences} A \emph{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 \emph{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{minipage}{.5\textwidth} \begin{tikzpicture}[shorten >=1pt,node distance=2.5cm,on grid,auto] \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 {$\mathtt{\Sigma}$} (1) (1) edge node {\ttt{b}} (2) edge [loop right] node {\ttt{a}} (1) (2) edge node {\ttt{b}} (0) edge [loop below] node {\ttt{a}} (2); \end{tikzpicture} \end{minipage} \begin{minipage}{.5\textwidth} \begin{table}[H] \setlength{\tabcolsep}{2em} \begin{tabular}{c|c|c|} \cline{2-3} \diagbox[dir=SW, width=2cm, height=0.6cm] & \ttt{a} & \ttt{b} \\ \hline \multicolumn{1}{|c|}{} & & \\ \hline \multicolumn{1}{|c|}{} & & \\ \hline \multicolumn{1}{|c|}{} & & \\ \hline \multicolumn{1}{|c|}{} & & \\ \hline \multicolumn{1}{|l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} \\ \hline \multicolumn{1}{|l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} \\ \hline \multicolumn{1}{|l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} \\ \hline \multicolumn{1}{|l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} \\ \hline \end{tabular} \end{table} \end{minipage} \bigskip \begin{center} Sample hard reset sequence: \underline{Write your answer here.} \end{center} \end{shaded} \annotate{Finding a hard reset sequence for this DFA is a lot easier if you take a few minutes to think about what the power automaton does.} \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. 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. \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}