Final Exam Solutions

Scores and Statistics

The distribution of grades for the final exam is as follows:

Rather than giving quartile scores, we thought we’d give quintile markers (based on scores before applying the curve mentioned below):

• 80th Percentile: 114.67 / 130 (88.21%)
• 60th Percentile: 102 / 130 (78.46%)
• 40th Percentile: 92 / 130 (70.77%)
• 20th Percentile: 78 / 130 (60%)

The median exam score was 73%, but we applied a curve to this exam that brought the median to 77.1%. Note that the curve did not add a constant number of points to everyone's scores; instead, it was based on a formula that adjusted different scores by slightly varying degrees. However, everyone received a boost to their scores to account for the difficulty of the exam, and the curve did not change anyone's relative ranking when sorting the final exam scores.

In addition to curving the final exam, we took the difficulty of the exam into account when assigning final letter grades this quarter.

Regrade requests are now open and will close on Monday, March 30, at 11:59 PM. Before submitting a regrade request, please be sure to see Sean's announcement on Ed about requirements for structuring such requests.

Problem One: Building Up vs. Building Down

Suppose we want to prove the following theorem by induction:

Theorem: For all natural numbers $n$, every graph with $n$ nodes contains exactly one enlightened path for each node in the graph.

Assuming (1) that we have a formal mathematical definition for “enlightened path,” (2) that we follow the build-up and build-down conventions established in class, and (3) that it is indeed possible to prove this theorem by induction (with only one base case), which of the following statements is true about how we should approach our proof by induction for the above theorem? Select all that apply. You may need to select multiple options, or no options at all. No justification is necessary.

Problem Two: Proof by Induction

Given two integers $a$ and $b$, we say that $a$ divides $b$ (written mathematically as $a\ |\ b$) if and only if there is some integer $z$ such that $b = az$. For example, we say $7\ |\ 14$ because there is an integer $z$ (namely, $z = 2$) such that $14 = 7z$.

Theorem: For all $n \in \naturals$, $10\ |\ (9^{n+1} + 7^{2n})$.

Prove the above theorem by induction, with the following restrictions:

• You must use an inductive proof. A proof that does not use induction may receive zero credit.
• Be sure to define a predicate in your proof.
• Please proceed with a single base case.
• We are expecting a rigorous proof that, among other things, makes use of the formal definition of what it means for one integer to divide another.

Hint #1: As you work through the algebra in this proof, if you find an integer $x$ that is close to a multiple of 10 (i.e., ± 1), you might find it helpful to rewrite that integer as $(x + 1)$ or $(x - 1)$, as appropriate. For example, 301 could be rewritten as $(300 + 1)$, or 299 could be rewritten as $\text{(300 – 1).}$

Hint #2: We anticipate Hint #1 will be more useful after you have massaged the equation that pops up in your inductive step to move toward a form that mirrors your inductive hypothesis (particularly in terms of your exponents). Applying Hint #1 too early might not lead anywhere productive.

Problem Three: Automata and Regular Expressions

Consider the automaton A and regular expression R that follow.

1. How can we tell that automaton $A$ is an NFA and not a DFA?

   It has $\varepsilon\text{-transitions}.$

2. Does taking the transition labeled $\varepsilon_{lower}$ lead to the acceptance of any strings starting with $b$ that cannot be accepted by taking the transition labeled $\varepsilon_{upper}$? If so, give one such string. Otherwise, write “NONE.”

   Any string that begins and ends with $b$ will suffice. For example: $b$

3. Does taking the transition labeled $\varepsilon_{lower}$ lead to the acceptance of any strings starting with $a$ that cannot be accepted by taking the transition labeled $\varepsilon_{loweupper}$? If so, give one such string. Otherwise, write “NONE.”

   Any string that begins with $a$ and ends with $b$ will suffice. For example: $ab$

4. Give a short string that is in $\mathscr{L}(A)$ but not $\mathscr{L}(R)$. If there is no such string, write “NONE.”

   $\varepsilon$ (this is the only such string)

5. Give a short string that is in $\mathscr{L}(R)$ but not $\mathscr{L}(A)$. If there is no such string, write “NONE.”

   NONE

6. After scrutinizing the NFA above, give the simplest (smallest) regular expression for $\mathscr{L}(A)$.

   We accepted all of the following:

   • $\Sigma^{*}$
   • $(a^* b^*)^*$
   • $(a? b?)^*$
   • $(a \cup b)^{*}$
   • $(a^* \cup b^*)^{*}$

   Technically, because this is an NFA, we don't know for certain whether $\Sigma = \set{a, b}\text{,}$ but we don't think it's unreasonable for someone to have made that assumption during the exam.

   We also accepted the use of the $\suchthat$ symbol in place of $\cup$ since that notation was permitted in regular expressions submitted as part of Problem Set 7. Note that we did not, however, accept $\set{a, b}^{*}\text{,}$ which is not a valid regular expression despite being a correct definition of the NFA's language using set theoretic notation.

Problem Four: Context-Free Grammars

Let $G_1$ be the following CFG:

Let $G_2$ be the following CFG:

Based on the CFGs above, answer the questions that follow:

1. Without using set builder notation, give the set of all strings in $\mathscr{L}(G_1) - \mathscr{L}(G_2)$.

   $\varnothing$

1. Without using set builder notation, give the set of all strings in $\mathscr{L}(G_2) - \mathscr{L}(G_1)$.

   $\set{qxr, rxq}$

Problem Five: Properties of Regular Languages

Prove or disprove the following statement:

Claim: If $L_1$ and $L_2$ are languages where $L_2$ is regular and $L_1 \subseteq L_2\text{,}$ then $L_1$ is also regular.

If proving this claim, we are expecting a response that proceeds formally, is careful in how it introduces variables, and abides by the proofwriting style conventions for this class. If disproving this claim, you can break from convention and provide a counterexample without justification. Check either the “Proof” or “Disproof” box below to let us know which option you choose.

Problem Six: Quick Check-in

Problem Seven: Graphing Out Languages

For the purposes of this problem, let’s define the following sets:

$\hspace{1.5cm}$ Let $𝔸 = \set{x \suchthat x \text{ is a lowercase letter in the English alphabet}}\text{.}$

$\hspace{1.5cm}$ Let $𝔼 = \set{w \in 𝔸^* \suchthat w \text{ is a a valid English word}}\text{.}$

$\hspace{1.5cm}$ Let $𝕍 = \set{v_x \suchthat x \in A}\text{.}$

$\hspace{1.5cm}$ Let $𝔾 = \set{G \suchthat G = (V, E) \text{ is a graph with } V = 𝕍}\text{.}$

Let $f:\powerset{𝔼} \rightarrow 𝔾$ be the function defined as follows: $f(X) = (𝕍, E)\text{,}$ the graph where $𝕍$ is as defined above and $\set{v_x, v_y} \in E$ if and only if $x ≠ y$ and there exists a string $w ∈ X$ where $w$ contains both $x$ and $y$.

Let $W = \set{\text{goose}, \text{egg}}\text{.}$ Answer the following questions about $f(W)$. No justification is required.

1. How many nodes are there in $f(W)$?

   26

2. What is the degree of node $v_\textbf{e}$ in $f(W)$? Here, e is the letter e, not a placeholder variable.

   3

3. How many edges are in $f(W)$?

   6

Answer the following questions about $f(𝔼)$. No justification is required.

4. How many nodes are there in $f(𝔼)$?

   26

5. What is the degree of node $v_\textbf{e}$ in $f(𝔼)$? Here, e is the letter e, not a placeholder variable.

   25

6. Prove there is a path of length 2 from $v_\textbf{z}$ to $v_\textbf{x}$ in $f(𝔼)$. Here, z and x are actual letters, not placeholder variables.

   We will show there is a path of length 2 from $v_\textbf{z}$ to $v_\textbf{x}$ in $f(𝔼)$. To see this, note that “zoo” $\in 𝔼$ and “ox” $\in 𝔼\text{.}$ Since “zoo” $\in 𝔼$ and “zoo” contains letters z and o, we have $\set{v_\textbf{z}, v_\textbf{o}} \in 𝔼\text{.}$ Similarly, since “ox” $\in 𝔼$ and “ox” contains letters o and x, we have $\set{v_\textbf{o}, v_\textbf{x}} \in 𝔼\text{.}$ Given those two edges are in 𝔼, we know $v_\textbf{z}, v_\textbf{o}, v_\textbf{x}$ is a path in $f(𝔼)$, and that is path of length 2 from $v_\textbf{z}$ to $v_\textbf{x}\text{,}$ as required. $\qed$

   Key idea: We needed to find two words where one contained ‘z’, the other contained ‘x,’ and both words had some other letter in common. Alternatively, a single word containing ‘z’, ‘x’, and one other letter would do the trick (e.g., “contextualize” and “exercise”).

   Common Errors: The most common error we saw in this problem was that many people did not proceed as if proving an existentially quantified statement. Remember, when proving an existential, your obligation is to go on an expedition to find a specific example that validates the theorem and then to present it to the reader.

   We also saw many solutions that did not use the correct notation for nodes in the graph or for articulating paths, set membership, or the presence of edges in the graph. Some solutions also used incorrect verbiage to describe graph structures (e.g., describing nodes as being "connected" rather than "adjacent," or referring to letters or words as if they themselves were nodes).

   A few responses attempted to rely on the result from 7(e) to prove this theorem, which we cannot do without proving that result, as well.

Note that the remaining parts of this question no longer focus on $f(𝔼)$. No justification is required for your responses.

7. True or False: For all $X \in \powerset{𝔼}\text{,}$ the length of a longest path in $f(X)$ cannot exceed $\abs{X}$.

   FALSE

   Consider, for example, $f(W)$ (for $W = \set{\text{goose}, \text{egg}}$, as defined above). We have $\abs{W} = 2$, but $f(W)$ has a path of length 3 (e.g., $v_\textbf{g}, v_\textbf{o}, v_\textbf{e}, v_\textbf{s}$), which exceeds 2.

8. True or False: For all $X \in \powerset{𝔼}\text{,}$ the length of a longest path in $f(X)$ cannot be less than $\abs{X}$.

   FALSE

   Consider, for example, the set $Y = \set{\text{a}}\text{.}$ We have $\abs{Y} = 1$, but the longest path in $f(Y)$ has length 0, which is less than 1.

9. Fill in the blanks below to demonstrate (very informally) that $f$ is not injective. Use the blanks only to give definitions for the sets $X$, $Y$, $V$, and $E\text{.}$ You do not have to write anything else. (The blank for $E$ is extra long in case you need space for that set. We do not want you to write anything else in that space. No concluding sentences are needed.)

   To show that $f$ is not injective, we could let $X = \underline{\hspace{4cm}}$ and $Y = \underline{\hspace{4cm}}\text{.}$ Both sets give rise to the graph $f(X) = f(Y) = (V, E)$ where $V = \underline{\hspace{4cm}}$ and $E = \underline{\hspace{4cm}}\text{.}$

   Here is one possibility:

   $\hspace{0.7cm}$ $X = \set{\text{goose}}$

   $\hspace{0.7cm}$ $Y = \set{\text{goose}, \text{egg}}$

   $\hspace{0.7cm}$ $V = 𝕍$

   $\hspace{0.7cm}$ $E = \set{\set{v_g, v_o}, \set{v_g, v_s}, \set{v_g, v_e}, \set{v_o, v_s}, \set{v_o, v_e}, \set{v_s, v_e}}$

   Key idea: The key idea here is that $X$ and $Y$ need to be chosen in such a way that any two letters, $x$ and $y$, appear together in some word in $X$ if and only if they appear together in some word in $Y$.

   Common Errors: The most common error we saw was restricting $V$ to a proper subset of $\mathbb{V}$ based only on the letters from the words in $X$ and $Y$. For example, for $X = \set{\text{cat}}$ and $Y = \set{\text{act}}\text{,}$ one might say $V = \set{v_c, v_a, v_t}\text{,}$ when in actuality, we should have $V = \mathbb{V}$ (which contains 26 nodes).

   Other common errors included using letters to represent nodes (rather than the $v_x$ notation introduced in the problem) and using (ordered, pairs) rather than {unordered pairs} to denote edges.

Problem Eight: Distinguishability

Let $\Sigma = \set{a, b}$ and consider the following language $L\text{:}$

$L = \set{w \in \Sigma^* \suchthat w \text{ has even length and its first half does not equal its second half}}\text{.}$

In Problem Set 7, we introduced this language and asked for a distinguishing set for $L$ containing four strings. It turns out that any two distinct strings in $\Sigma^*$ are distinguishable with respect to $L\text{!}$ We will partially prove that this is the case by proving the following:

Lemma 1: Any two distinct strings $x$ and $y$ over $\set{a, b}$ where $\abs{x} = \abs{y}$ are distinguishable with respect to $L$.

Lemma 2: Any two distinct strings $x$ and $y$ over $\set{a, b}$ where $\abs{x}$ and $\abs{y}$ have different parities are distinguishable with respect to $L\text{.}$

Notes and restrictions:

• You must write a direct proof for each lemma. An indirect proof or proof by induction may receive zero credit.
• Note that both lemmas indicate that $x$ and $y$ are distinct strings.
• We are expecting rigorous proofs that, among other things, make use of the formal definition of distinguishability.
• Recall that two integers have the same parity if they are either both even or both odd; otherwise, they do not have the same parity.

Lemma 1

Lemma 2

Problem Nine: A Quick Visit to the $A_{TM}$

Let $M$ be a Turing machine and $w$ a string. Suppose we know $\langle M, w \rangle \notin A_{TM}\text{.}$ Consider what that means about each of the following statements. To be clear, we are not asking which of these statements are equivalent to $\langle M, w \rangle \notin A_{TM}\text{.}$ We are asking, given that we know $\langle M, w \rangle \notin A_{TM}\text{,}$ which of these statements must also be true, which of them must be false, and which of them could either be true or false (i.e., we do not know for certain whether they are true).

1. $U_{TM}$ accepts $\langle M, w \rangle$

   $\square$ This statement must also be true.
   $\checkmark$ This statement must be false.
   $\square$ Cannot be determined.

2. $U_{TM}$ rejects $\langle M, w \rangle$

   $\square$ This statement must also be true.
   $\square$ This statement must be false.
   $\checkmark$ Cannot be determined.

3. $U_{TM}$ halts on $\langle M, w \rangle$

   $\square$ This statement must also be true.
   $\square$ This statement must be false.
   $\checkmark$ Cannot be determined.

4. $U_{TM}$ loops on $\langle M, w \rangle$

   $\square$ This statement must also be true.
   $\square$ This statement must be false.
   $\checkmark$ Cannot be determined.

5. $M$ accepts $w$

   $\square$ This statement must also be true.
   $\checkmark$ This statement must be false.
   $\square$ Cannot be determined.

6. $M$ rejects $w$

   $\square$ This statement must also be true.
   $\square$ This statement must be false.
   $\checkmark$ Cannot be determined.

7. $M$ halts on $w$

   $\square$ This statement must also be true.
   $\square$ This statement must be false.
   $\checkmark$ Cannot be determined.

8. $M$ loops on $w$

   $\square$ This statement must also be true.
   $\square$ This statement must be false.
   $\checkmark$ Cannot be determined.

9. $\langle U_{TM}, \langle M, w \rangle \rangle \in A_{TM}$

   $\square$ This statement must also be true.
   $\checkmark$ This statement must be false.
   $\square$ Cannot be determined.

10. $M$ is a decider for some language.

    $\square$ This statement must also be true.
    $\square$ This statement must be false.
    $\checkmark$ Cannot be determined.

11. $M$ is a recognizer for some language.

    $\checkmark$ This statement must also be true.
    $\square$ This statement must be false.
    $\square$ Cannot be determined.

    Note: We know $M$ is a Turing machine, and every Turing machine is a recognizer for some language: the language of all strings it accepts. This is true even if $M$ either loops on or rejects every string (in which case its language is simply the empty set).

12. If $w = \langle M \rangle$, then $\langle M \rangle \in L_D\text{.}$

    $\checkmark$ This statement must also be true.
    $\square$ This statement must be false.
    $\square$ Cannot be determined.

13. If $w = \langle M \rangle$, then $L_D$ is decidable.

    $\square$ This statement must also be true.
    $\checkmark$ This statement must be false.
    $\checkmark$ Cannot be determined.

    Note: We accepted either of the answers marked above because there are two ways to interpret this question:

    (1) This can be interpreted as asking about the truthiness of a proposition involving implication. We know if $w = \langle M \rangle$ is false, the implication is vacuously true. If $w = \langle M \rangle$ is true, then the implication is false (because we know the consequent is false, and $T \rightarrow F$ is false). Since the implication could be either true or false, the truthiness of the given statement cannot be determined.

    (2) This can be interpreted to mean that we want you to assume $w = \langle M \rangle$ and then tell us what that would mean about the truthiness of the statement, “$L_D$ is decidable.” Regardless of whether $w = \langle M \rangle\text{,}$ we know $L_D$ is not decideable, and so we would answer here that “$L_D$ is decidable” is certainly false.

Problem Ten: Having Some Difficulty

Suppose $QUAGGLE$ is a language in NP-Complete. Indicate what that reveals about the truthiness of each of the following statements. In answering these questions, keep in mind that we do not know for certain whether $P = NP$.

1. $QUAGGLE$ is at least as hard as $SAT\text{.}$

   $\checkmark$ This statement is true.
   $\square$ This statement is false.
   $\square$ Unknown / cannot be determined.

2. $SAT$ is at least as hard as $QUAGGLE\text{.}$

   $\checkmark$ This statement is true.
   $\square$ This statement is false.
   $\square$ Unknown / cannot be determined.

3. $QUAGGLE \leq_{p} SAT\text{.}$

   $\checkmark$ This statement is true.
   $\square$ This statement is false.
   $\square$ Unknown / cannot be determined.

4. $SAT \leq_{p} QUAGGLE\text{.}$

   $\checkmark$ This statement is true.
   $\square$ This statement is false.
   $\square$ Unknown / cannot be determined.

5. There exists a polynomial-time verifier for QUAGGLE.

   $\checkmark$ This statement is true.
   $\square$ This statement is false.
   $\square$ Unknown / cannot be determined.

6. There exists a polynomial-time decider for QUAGGLE.

   $\square$ This statement is true.
   $\square$ This statement is false.
   $\checkmark$ Unknown / cannot be determined.

7. QUAGGLE is decidable.

   $\checkmark$ This statement is true.
   $\square$ This statement is false.
   $\square$ Unknown / cannot be determined.

8. If we find a polynomial-time verifier for QUAGGLE, that will mean $P = NP\text{.}$

   $\square$ This statement is true.
   $\checkmark$ This statement is false.
   $\square$ Unknown / cannot be determined.

9. $P \neq NP \rightarrow$ All problems in $NP$ are at least as hard as $QUAGGLE\text{.}$

   $\square$ This statement is true.
   $\square$ This statement is false.
   $\checkmark$ Unknown / cannot be determined.

   Note: If $P = NP$, the implication is vacuously true. If $P \neq NP$, the implication is false (since the consequent is false, and $T \rightarrow F$ is false).

10. QUAGGLE is at least as hard as all problems in NP.

    $\checkmark$ This statement is true.
    $\square$ This statement is false.
    $\square$ Unknown / cannot be determined.

Problem Eleven: The Lava Diagram

Below is a Venn diagram showing the overlap of different classes of languages we have studied. We have also included FINITE, the class of all languages containing only finitely many strings. We have also provided you a list of numbered languages. For each of those languages, draw where in the Venn diagram that language belongs. No justification is required. As an example, we have indicated where Languages $a$ and $b$ should go. Note that for typographical reasons, we skipped letters $i$, $l$, $n$, and $o$ in our list.

1. $L_D$ (given)

2. $\set{\text{baba}, \text{yaga}}$ (given)

3. $\set{\text{x}, \text{y}}^*$

   REG

   We can write a regular expression or create a DFA for this language, but it's non-finite, so it falls in REG.

4. $\set{ a^n b^n \suchthat n \in \naturals \text{ and } n \lt 10}$

   FINITE

   There are finitely many strings in this set, and so this one is FINITE.

5. $\set{ a^n b^n \suchthat n \in \naturals \text{ and } n \gt 10}$

   R

   There are infinitely many strings in this one, and it's a slight twist on $\set{ a^n b^n \suchthat n \in \naturals}\text{.}$ We could apply a Myhill-Nerode style argument to the language in this question to show that it is non-regular, but we know we can build a decider for that language (similar to the one we built in class for $\set{ a^n b^n \suchthat n \in \naturals}\text{),}$ so this one is in R.

6. $\set{\langle M \rangle \suchthat M \text{ is a TM that halts on at least one input}}$

   RE

   We could build a verifier for this language that takes as its certificate a $\langle w, k \rangle$ encoding, where $w$ is a string that $M$ halts on and $k$ is the number of steps it takes for $M$ to halt on $w$. The verifier could then simulate $M$ for $k$ steps and accept if $M$ has halted on $w$ at that point and reject otherwise. To see that this language is not in R, note that the halting problem reduces to this problem; if we had a decider for this, we would effectively have a decider for $HALT$. (We leave it to you as an exercise to consider how that would work.)

7. $\set{\langle M \rangle \suchthat M \text{ is a TM that halts on at least one input within 100 steps of execution}}$

   R

   This one is decidable. First, note that we only need to consider inputs of length $\leq 100$ if we want to check for strings where $M$ halts within 100 steps, because having a TM move the tape head through all the characters in an input string with $\gt 100$ characters would require more than 100 steps of execution. Because alphabets are finite, we have a finite number of possible input strings of length $\leq 100\text{.}$ Thus, we can just simulate $M$ on every possible possible input of length $\leq 100$ for up to 100 steps and see whether it halts.

   Note that although our decider would feed a finite number of finite-length strings to our TMs and simulate for a finite number of steps, that does not mean that the language we're deciding in this problem is finite! We could conceive of infinite TMs whose encodings would belong in this language.

8. $\set{\langle M \rangle \suchthat M \text{ is a TM whose string representation, } \langle M \rangle \text{ is a palindrome}}$

   R

   We can create a decider that determines whether an input string corresponds to a valid TM (our TM simulator does this!), and we have a decider for checking whether a string is a palindrome (we explored this idea in lecture), so this language is decidable. This language is not regular, though; we saw a Myhill-Nerode argument in class that checking for palindromes over $\set{a, b}$ exceeds what we can do with NFAs/DFAs, and the same basic argument applies when considering palindromes over any alphabet with two or more characters.

10. The language of the following grammar:

    $\hspace{2cm}$	$S$	$\rightarrow$	$XY \suchthat YX \suchthat \varepsilon$
    	$Y$	$\rightarrow$	$pXj \suchthat Xpj$
    	$X$	$\rightarrow$	$cookie$

    FINITE

    Note that none of these production rules are recursive. This grammar produces a finite number of strings, and so this language falls in FINITE.

11. $\set{\langle M \rangle \suchthat M \text{ is a TM that rejects the string representation of itself, } \langle M \rangle}$

    RE

    We can build a verifier for this language that takes as its certificate the number of steps $k$ that it takes for $M$ to reject $\langle M \rangle$. The verifier would simulate $M$ on $\langle M \rangle$ for $k$ steps and accept if $M$ reject within $k$ steps. Thus, this language must be in $RE$. We cannot, however, create a decider that determines whether an arbitrary TM $M$ will halt on $\langle M \rangle\text{;}$ to see this, we could construct a classical trickster where we predicate the trickster's behavior on the response of that decider in cases where the trickster happens to receive its own source code as its input. Accordingly, this language is not in $R$.

13. $\set{\langle M \rangle \suchthat M \text{ is a TM that does not accept the string representation of itself, } \langle M \rangle}$

    ALL

    This is $L_D$, which is our canonical example of a language that is unrecognizable and falls outside the bounds of what we can touch with a computer.

16. An arbitrary NP-Complete problem. (When placing this one in the Lava Diagram, assume $P \neq NP$.)

    R

    One of the key take-aways from our discussion of complexity theory was that we were focusing on decidable problems; $P$ and $NP$ are subsets of $R\text{.}$ We have no grounds to claim that all NP-Complete problems are regular, though, and so the answer for this one is $R$.

Bonus Questions

1. What topic did Sean stumble upon recently that this class seems to find particularly humorous?

   death / morbidity

   We also saw “67” as a frequent response to this question. 67 came up in class less recently than the intended answer (which came up on Wednesday of Week 10, and which Sean commented on at the time, given the class's reaction), but we still awarded partial credit for this response.

2. What is Sean’s favorite power-of-two fact to throw around in class? (Fill in the blanks.)

   2 to the power of $\underline{\textbf{30}}$ is approximately $\underline{\textbf{one billion}}\text{.}$