% % 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 % Updated for Winter 2020 by Cynthia Lee \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 \title{\vspace{-1.5cm} CS 103: Mathematical Foundations of Computing\\Problem Set \#8} \author{Your Name(s) Here} \date{\today} \lhead{Your Name(s) Here} \chead{Problem Set \#8} \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 \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}}} \usepackage{parskip} \newcommand{\lcurly}{\textbf{\ttt{\{}}} \newcommand{\rcurly}{\textbf{\ttt{\}}}} % end MZ \begin{document} \maketitle \section{Designing CFGs} For each of the following languages, design a CFG for that language. \textit{\textbf{Please use our online tool to design, test, and submit the CFGs in this problem}}. To use it, visit the CS103 website and click the ``CFG Editor'' link under the ``Resources'' header. You should only have one member from each team submit your grammars; tell us who this person is when you submit the rest of the problems through GradeScope. \begin{enumerate}[label*=\roman*.,ref=\roman*] \item Given $\Sigma = \{\ttt{a}, \ttt{b}, \ttt{c}\}$, write a CFG for the language $\{\ w \in \Sigma^*\ |\ w$ contains \ttt{aa} as a substring $\}$. For example, the strings \ttt{aa}, \ttt{baac}, and \ttt{ccaabb} are all in the language, but \ttt{aba} is not. \item Given $\Sigma = \{\ttt{a}, \ttt{b}\}$, write a CFG for the language $\{\ w \in \Sigma^*\ |\ w$ is \emph{not} a palindrome $\}$, the language of strings that are not the same when read forwards and backwards. For example, $\ttt{aab} \in L$ and $\ttt{baabab} \in L$, but $\ttt{aba} \not\in L$, $\ttt{bb} \not\in L$, and $\varepsilon \not\in L$. \annotate{Don't try solving this one by starting with the CFG for palindromes and making modifications to it. In general, there's no way to mechanically turn a CFG for a language L into a CFG for the language $\overline{L}$, since the context-free languages aren't closed under complementation. However, the idea of looking at the first and last characters of a given string might be a good idea.} \item Let $\Sigma$ be an alphabet containing these symbols: \begin{equation*} \emptyset \quad\quad \N \quad\quad \{ \quad\quad \} \quad\quad , \quad\quad \cup \end{equation*} We can form strings from these symbols which represent sets. Here's some examples: \begin{center} \begin{tabularx}{12cm}{X X X X} $\emptyset$ & $\{\emptyset, \N\} \cup \N \cup\ \emptyset$ & $\{\emptyset\} \cup \N \cup \{\N\}$ & $\{\emptyset, \emptyset, \emptyset\}$ \\[0.1cm] $\{\{\N, \emptyset\} \cup \{\emptyset\}\}$ & $\N \cup \{\N, \emptyset\}$ & $\{\}$ & $\{\N\}$ \\[0.1cm] $\{\emptyset, \{\emptyset, \{\emptyset\}\}\}$ & $\{\{\{\{\N\}\}\}\}$ & $\N$ & $\{\emptyset, \{\}\}$ \end{tabularx} \end{center} Notice that some of these sets, like $\{\emptyset, \emptyset\}$ are syntactically valid but redundant, and others like $\{\}$ are syntactically valid but not the cleanest way of writing things. Here's some examples of strings that don't represent sets or aren't syntactically valid: \begin{center} \begin{tabularx}{12cm}{X X X X} $\varepsilon$ & $\}\emptyset\{$ & $\emptyset\{\N\}$ & $\{\{\}$ \\[0.1cm] $\N, \emptyset, \{\emptyset\}$ & $\{, \N\}$ & $\{ \N \emptyset \},$ & $\{,\}$ \\[0.1cm] $\{\emptyset$ & $\}\} \N$ & $\{ \emptyset, \emptyset, \emptyset, \}$ & $\{\N, , , \emptyset\}$ \end{tabularx} \end{center} Write a CFG for the language $\{\ w \in \Sigma^*\ |\ w$ is a syntactically valid string representing a set $\}$. \\ When using the CFG tool, please use the letters \ttt{n}, \ttt{u}, and \ttt{o} in place of $\N, \cup,$ and $\emptyset$, respectively. \emph{Fun fact}: The starter files for Problem Set One contain a parser that's designed to take as input a string representing a set and to reconstruct what set that is. The logic we wrote to do that parsing was based on a CFG we wrote for sets and set theory. Take CS143 if you're curious how to go from a grammar to a parser! \annotate{Test your CFG thoroughly! In Fall 2017, a quarter of the submissions we received weren't able to derive the string $\{\emptyset, \emptyset, \emptyset\}$.} \annotate{As a hint, as is often the case when writing CFGs, we recommend that you use different nonterminals to represent different components of the string. For example, structure of a comma-separated list is very different from the structure of an expression combining multiple sets together.} \end{enumerate} \begin{shaded} Write the SUNetID of the person who submitted the CFGs here. \end{shaded} \pagebreak \section{The Complexity of Addition} This problem explores the following question: \begin{center} \emph{How hard is it to add two numbers?} \end{center} Suppose that we want to check whether $x + y = z$, where $x, y,$ and $z$ are all natural numbers. If we want to phrase this as a problem as a question of strings and languages, we will need to find some way to standardize our notation. In this problem, we will be using the \textit{\textbf{unary number system}}, a number system in which the number $n$ is represented by writing out $n$ 1's. For example, the number 5 would be written as 11111, the number 7 as 1111111, and the number 12 as 111111111111. Given the alphabet $\Sigma = \{\ttt{1}, \ttt{+}, \ttt{=}\}$, we can consider strings encoding $x + y = z$ by writing out $x, y,$ and $z$ in unary. For example: \begin{align*} 4 + 3 &= 7 \text{ would be encoded as }\ttt{111+1111=1111111} \\ 7 + 1 &= 8 \text{ would be encoded as }\ttt{1111111+1=11111111} \\ 0 + 1 &= 1 \text{ would be encoded as }\ttt{+1=1} \end{align*} Consider the alphabet $\Sigma = \{1, +, =\}$ and the following language, which we'll call \textit{ADD}: \begin{equation*} \{\ \ttt{1}^m\ttt{+1}^n\ttt{=1}^{m+n} \mid m, n \in \N\ \} \end{equation*} For example, the strings \ttt{111+1=1111} and \ttt{+1=1} are in the language, but \ttt{1+11=11} is not, nor is the string \ttt{1+1+1=111}. \begin{enumerate}[label*=\roman*.,ref=\roman*] \item Prove or disprove: the language \textit{ADD} defined above is regular. \begin{shaded} Provide a proof or disproof here. \end{shaded} \item Write a context-free grammar for \textit{ADD}, showing that \textit{ADD} is context-free. (Please submit your CFG online.) \annotate{You may find it easier to solve this problem if you first build a CFG for this language where you're allowed to have as many numbers added together as you'd like. Once you have that working, think about how you'd modify it so that you have exactly two numbers added together on the left-hand side of the equation.} \begin{shaded} Write the SUNetID of the person who submitted the CFG here. \end{shaded} \end{enumerate} \pagebreak \section{The Complexity of Pet Ownership} This problem explores the following question: \begin{center} \textit{\textbf{How hard is it to walk your dog without a leash?}} \end{center} Let's imagine that you're going for a walk with your dog, but this time don't have a leash. As in Problem Set Six and Problem Set Seven, let $\Sigma = \{\ttt{y}, \ttt{d}\}$, where $\ttt{y}$ means that you take a step forward and $\ttt{d}$ means that your dog takes a step forward. 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 that you take two steps forward, then your dog takes two steps forward. Let \textit{DOGWALK} $ = \{w \in \Sigma^*\ |\ w$ describes a series of steps where you and your dog arrive at the same point$\}$. For example, the strings \ttt{yyyddd}, \ttt{ydyd}, and \ttt{yyyddddddyyy} are all in \textit{DOGWALK}. \begin{enumerate}[label*=\roman*.,ref=\roman*] \item Prove or disprove: the language \textit{DOGWALK} defined above is regular. \begin{shaded} Provide a proof or disproof here. \end{shaded} \pagebreak \item Write a context-free grammar for \textit{DOGWALK}, showing that \textit{DOGWALK} is context-free. (Please submit your CFG online.) \annotate{Be careful, and test your CFG! Check the lecture slides on CFGs for examples of grammars that don't work, and make sure you can articulate why those grammars are incorrect.} \begin{shaded} Write the SUNetID of the person who submitted the CFG here. \end{shaded} \end{enumerate} \pagebreak \section{Equivalence Classes and Regular Languages, Part Two} On Problem Set Seven, you explored the \emph{indistinguishability} relation for $L$, denoted $\equiv_L$, defined as \begin{center} $x \equiv_L y \quad \text{if} \quad \forall w \in \Sigma^*.(xw \in L \leftrightarrow yw \in L).$ \end{center} You specifically proved that for any language $L$, the relation $\equiv_L$ is an equivalence relation and that any DFA for $L$ must have at least $I(\equiv_L)$ states. In this problem, you're going to prove an amazing result: \begin{center} \emph{Theorem:} If $L$ is a language where $I(\equiv_L)$ is finite, then $L$ is regular. \end{center} In other words, if you know absolutely nothing about a language other than there are finitely many equivalence classes of the $\equiv_L$ relation, then somewhere out there, there must be a DFA for $L$! Let $L$ be an arbitrary language over some alphabet $\Sigma$ where $I(\equiv_L)$ is finite. We are going to prove that $L$ is regular by defining a 5-tuple $(Q, \Sigma, \delta, q_0, F)$ for this language $L$. The key insight behind this proof is how to choose $Q$. Specifically, we will choose $Q$ to be the set of equivalence classes of $\equiv_L$: \begin{center} $Q = \{ [w]_{\equiv_L} \mid w \in \Sigma^* \}.$ \end{center} It might seem strange to have the states of a DFA be sets, but then again, you've seen something like this before. In Problem Set Six, when working through the subset construction, you created a DFA whose states literally were sets of states of some particular NFA. \begin{enumerate}[label=\roman*.] \item Explain why $Q$ is finite. This should take you at most a sentence or two. \begin{shaded} Write your explanation here. \end{shaded} \end{enumerate} We now need to figure out how to pick a start state and wire up our transitions. Our goal will be to define $q_0$ and $\delta$ so that our DFA has the following property: if you run $w$ through this DFA, the state you end up in corresponds to $[w]_{\equiv_L}$. It turns out that choosing $q_0$ and $\delta$ as follows makes this work: \begin{center} $q_0 = [\varepsilon]_{\equiv_L} \qquad\qquad\qquad \delta([x]_{\equiv_L}, a) = [xa]_{\equiv_L}.$ \end{center} Of course, you shouldn't take our word for it. You should prove that these choices make everything work! \begin{enumerate}[resume*] \item Prove that for any string $w \in \Sigma^*$, we have $\delta^*(w) = [w]_{\equiv_L}$. \annotate{For help with the definition of $\delta^*$, check the pset8 web page, which has a 1-page explainer.} \begin{shaded} Provide a proof here. \end{shaded} \end{enumerate} To seal the deal, we need to choose our set of accepting states. We'll define $F$ as follows: \begin{center} $F = \{[w]_{\equiv_L} \mid \exists x \in [w]_{\equiv_L}. x \in L \}.$ \end{center} In other words, $F$ is the set of all equivalence classes containing at least one string in $L$. \begin{enumerate}[resume*] \item In the 1-page explainer for $\delta^*$ (see pset8 web page), you saw that we can formally define $\mathscr{L}(D) = \{ w \in \Sigma^* \mid \delta^*(w) \in F \}$. Prove that with this choice of $F$, we have $\mathscr{L}(D) = L$. \annotate{There is a ton of formal notation here, but at the end of the day, this question is just asking you to prove that two sets are equal. Think way back to Problem Set One. What's the easiest way to do this?} \annotate{Your proof should use the formal definitions provided here rather than higher-level concepts like ``the DFA accepts w'' or ``run the DFA on w.'' Also, perhaps a result from Problem Set Seven would be useful here?} \begin{shaded} Provide a proof here. \end{shaded} \end{enumerate} By combining the two theorems you've explored about indistinguishability -- the one you proved last time, and the one from above -- we get this fundamental result: \begin{center} \emph{Theorem (Myhill-Nerode):} A language $L$ is regular if and only if $I(\equiv_L)$ is finite. Furthermore, if $I(\equiv_L)$ is finite, the smallest possible DFA for $L$ has exactly $I(\equiv_L)$ states. \end{center} This result formalizes the intuition we've had about regular languages corresponding to problems you can solve with only finite memory. The ``memory'' you need corresponds to remembering which equivalence class the string you've seen so far happens to fall into. If you talk to CS theory folk and mention ``the Myhill-Nerode theorem,'' they'll assume you're talking about the above theorem! The version we saw in lecture is just a special case of this more general one. \pagebreak \section{TMs, Formally} Just as it's possible to formally define a DFA using a 5-tuple, it's possible to formally define a TM as an 8-tuple $(Q, \Sigma, \Gamma, B, q_0, Y, N, \delta)$ where \begin{itemize} \item $Q$ is a finite set of states, which can be anything; \item $\Sigma$ is a finite, nonempty set called the \textit{\textbf{input alphabet}}; \item $\Gamma$ is a finite, nonempty set called the \textit{\textbf{tape alphabet}}, where $\Sigma \subseteq \Gamma$; \item $B \in \Gamma - \Sigma$ is the \textit{\textbf{blank symbol}}; \item $q_0$ is the start state, where $q_0 \in Q$; \item $Y \subseteq Q$ is the set of \textit{\textbf{accepting states}}; \item $N \subseteq Q$ is the set of \textit{\textbf{rejecting states}}, where $Y \cap N = \emptyset$; and \item $\delta$ is the \textit{\textbf{transition function}}, described below. \end{itemize} Remember that the definition is the official arbiter of what is legal and what isn’t, so if the definition doesn’t preclude something, it’s legal regardless of how counterintuitive or weird it might be. This question explores some aspects of the definition. \begin{enumerate}[label*=\roman*.,ref=\roman*] \item Is it possible to have a TM with no states? Justify your answer. \begin{shaded} Provide your answer and justification here. \end{shaded} \item Is it possible to have a TM with no \textit{accepting} states? Justify your answer. \begin{shaded} Provide your answer and justification here. \end{shaded} \item Is it possible to have a TM with no \textit{rejecting} states? Justify your answer. \begin{shaded} Provide your answer and justification here. \end{shaded} \item Why is the restriction $Y \cap N = \emptyset$ there? Justify your answer. \begin{shaded} Provide your answer and justification here. \end{shaded} \item Is it possible to have a TM where $\Sigma = \Gamma$? Justify your answer. \begin{shaded} Provide your answer and justification here. \end{shaded} \end{enumerate} Now, let's talk about the transition function. As with DFAs, the transition function of a Turing machine is what formally defines the transitions. If $q$ is a state in a TM that isn't an accepting state or a rejecting state and $a$ is a symbol that can appear on the TM's tape, then \begin{equation*} \delta(q, a) = (r, b, D) \end{equation*} where $r$ is the new state to transition into, $b$ is the symbol to write back to the tape, and $D$ is either $L$ for ''move left'' or $R$ for ''move right.'' Because TMs immediately stop running after entering an accepting or rejecting state, the $\delta$ function should not be defined for any state $q$ that's either accepting or rejecting. Aside from this, $\delta$ should be defined for every combination of a (non-accepting, non-rejecting) state $q$ and any symbol $a$ that can appear on the tape. \begin{enumerate}[resume*] \item Based on the above description of $\delta$, what should the domain of $\delta$ be? What should it codomain be? Answer this question by filling in the following blanks, and briefly justify your answer. \annotate{In class, we said that any missing transitions in a TM implicitly reject. By that, we didn't mean that the TM's transition function can be undefined on certain inputs. Instead, it means ``if we don't draw in a transition in a picture representing the TM, it means that the transition does exist and goes to a rejecting state, but we were just too lazy to draw it in.'' So you should assume that every transition not drawn in a picture of a TM really is there and really goes to some rejecting state.} \annotate{Also, take a moment to appreciate the fact that you can read the notation in this question and understand what it means! Could you imagine doing that at the start of the quarter?} \begin{shaded} \begin{center} $\delta$: \underline{Write your answer here} $\rightarrow$ \underline{and here.} \end{center} Provide justification here. \end{shaded} \end{enumerate} \pagebreak \section{Regular and Decidable Languages} In class, we alluded to the fact that \textbf{REG} (the class of all regular languages) is a subset of \textbf{R} (the class of all decidable languages), but we never actually justified this claim. Describe a construction that, given a DFA $D$, produces a decider $D'$ where $\mathscr{L}(D) = \mathscr{L}(D')$. Briefly justify why the TM $D'$ you construct is a decider and why it accepts precisely the strings that $D$ accepts. Illustrate your example by applying it to a small DFA $D$ of your choice. Although you have a formal 5-tuple definition of a DFA and a formal 8-tuple definition of a TM at your disposal, we're not expecting you to write your solution at that level of detail. \annotate{Remember that DFAs and TMs work completely differently with regards to accepting and rejecting states and that the transitions in TMs have a very different structure than the transitions in DFAs!} \begin{shaded} Provide an answer here. \end{shaded} \pagebreak \section{What Does it Mean to Solve a Problem?} Let $L$ be a language over $\Sigma$ and $M$ be a TM with input alphabet $\Sigma$. Below are three potential traits of $M$: \begin{center} \begin{minipage}[t]{.6\textwidth} \begin{enumerate} \item $M$ halts on all inputs. \item For any string $w \in \Sigma^*$, if $M$ accepts $w$, then $w \in L$. \item For any string $w \in \Sigma^*$, if $M$ rejects $w$, then $w \not\in L$.\\ \end{enumerate} \end{minipage} \end{center} At some level, for a TM to claim to solve a problem, it should have at least some of these properties. Interestingly, though, just having two of these properties doesn't say much. \begin{enumerate}[label*=\roman*.,ref=\roman*] \item Prove that if $L$ is any language over $\Sigma$, then there is a TM $M$ that satisfies properties (1) and (2). \begin{shaded} Provide a proof here. \end{shaded} \item Prove that if $L$ is any language over $\Sigma$, then there is a TM $M$ that satisfies properties (1) and (3). \begin{shaded} Provide a proof here. \end{shaded} \item Prove that if $L$ is any language over $\Sigma$, then there is a TM $M$ that satisfies properties (2) and (3). \begin{shaded} Provide a proof here. \end{shaded} \item Suppose that $L$ is a language over $\Sigma$ for which there is a TM $M$ that satisfies properties (1), (2), and (3). What can you say about $L$? Prove it. \begin{shaded} Provide your answer and proof here. \end{shaded} \end{enumerate} \annotate{The whole point of this problem is to show that you have to be extremely careful about how you define ``solving a problem,'' since if you define it incorrectly then you can ``solve'' a problem in a way that bears little resemblance to what we'd think of as solving a problem. Keep this in mind as you work through this one.} \section*{Optional Fun Problem One: TMs and Regular Languages (Extra Credit)} Let $M$ be a TM with the following property: there exists a natural number $k$ such that after $M$ is run on any string $w$, $M$ always halts after at most $k$ steps. Prove that $\mathscr{L}(M)$ is regular. \begin{shaded} Provide a proof here. \end{shaded} \end{document}