Question 1 (30):  Five of the dogs currently on Dave’s block form the set D  =  {b, c, i, k, m}, consisting of Blaze, Clover, Indy, Kik´e, and Mango. We define three predicates on the set D , such that R(x) means  “dog x is a retriever”, S(x, y) means  “dog x is smaller than dog y”, and L(x, y) means “dog x is larger than dog y”.

We assume that both the relations L and S are each antireflexive, antisymmetric, and tran- sitive.  We also assume that Vx : Vy : L(x, y) 4 S(y, x), and that no two dogs have exactly the same size (in symbols, Vx : Vy : (x  y) → (S(x, y)) V S(y, x))).

We also define two more predicates on D in terms of the first two, so that LR(x) means “dog x is larger than some retriever” and SR(x) means “dog x is smaller than some retriever”.

(a, 10):  Translate the following statements as indicated.

● Statement I: (into symbols, using only quantifiers, R, and S) Mango, who is not a

retriever, is not smaller than any retriever.

-R(m) A -ax : R(x) A S(m, x)

● Statement II: (into English) Vx : SR(x) · LR(x).

Any dog is either smaller than some retriever, or is larger than some retriever, but not both.

● Statement III: (into English) ax : L(b, x) A -R(x).

There exists some dog x such that Blaze is larger than x and x is not a retriever.

● Statement IV:  (into symbols) Both Blaze and Kik´e are each smaller than every retriever.

Vx : R(x) → (S(b, x) A S(k, x))

● Statement V: (into English) (S(b, c) 4 S(b, i)) A (S(b, k) · S(b, m))

Blaze is smaller than Clover if and only if Blaze is smaller than Indy, and Blaze is smaller than either Kik´e or Mango, but not both.

of them must have size between the other two, and that dog z would satisfy SR(z) and LR(z), violating II. (Another way to see this would be to look at cases – let x and y be two retrievers such that (without loss of generality) S(x, y). Then if there were a third retriever z, if S(z, x) we have a violation of II with x, if S(x, z) and S(z, y) we have a violation with z, and if S(y, z) we have a violation with y .

forget to handle the case of n = 0, because 0 is a natural. Remember that sums with no terms always equal 0.

Let P (n) be the statement     n   =  _  .

The base case P (0) is true because the LHS is zero, as an empty sum, and the RHS =  _  = 0.

Assume P (n), and consider the sum       , which is equal to       plus  , which by the IH is  _  +  . We can rewrite this as  _  +  =  _  , as desired.

CICS planned a big banquet to celebrate some large donations, and they planned to seat each of 2n guests at a long table, with the seats {1, 2, . . . , 2n} in a single row.   But with the advent of the Omicron COVID variant, they had to reduce the guest list, even though there are still n + 1 important guests that still need to be invited.

(b, 10)  The first guidelines say that no two guests may sit in adjacent seats (such as i and i + 1). Prove by induction, for any positive n, that we cannot seat n + 1 people among positions {1, 2, . . . 2n} without using at least one pair of adjacent seats.  Prove this by ordinary induction.

Let P (n) be the statement that if n + 1 guests are seated in 2n positions, there must be two adjacent guests.

The base case is P (1), which says that if there are 1 + 1 guests seated in 2 . 1 positions, some pair must be adjacent.   This is true because positions  1 and  2 must both be occupied.

Now assume P (n) as the IH, and consider n + 1 + 1 guests seated in 2(n + 1) positions. If seats 2n + 1 and 2n + 2 are both occupied, they form a violation because they are adjacent. But if one of these seats are vacant, then there are at least n + 1 guests seated in positions {1, . . . , 2n}, and the IH says that these cannot be seated legally.

CICS asked for new guidelines and were told now that seats could be adjacent, as long as they don’t use any pair of seats numbered x and y where x divides the number y.  For example, this cannot be done with n = 2, because there are four choices to take n+1 = 3 of the 2n = 4 positions and all of them fail:  {1, 2, 3} and {1, 2, 4} have 1 dividing 2, {1, 3, 4} has 1 dividing 3, and {2, 3, 4} has 2 dividing 4. They set out to prove that for any positive n this task is impossible.  Let P (n) be the statement “In any set of n + 1 positions among positions {1, 2, . . . , 2n}, some position is chosen whose number divides the number of another position chosen.”

(c, 5)  Prove the base case, state the inductive hypothesis, and state the inductive goal.       We are asked to prove this statement for positive n, so the base case is n = 1.  It says that we cannot seat two guests in positions 1 and 2 without a violation, and this is true because 1 divides 2.

The IH says that we cannot seat n + 1 guests in seats {1, . . . , 2n} without a violation.  The IG says that we cannot seat n + 2 guests in seats {1, . . . , 2n + 2 without a violation.

(d, 5)  Prove the case of the inductive goal where at least one of the positions 2n+ 1 or 2n+ 2 is left vacant.

If one of those two seats is left vacant, we would have at least n + 1 guests in positions {1, . . . , 2n}, violating the IH.

(e, 10XC)  Finish the proof by completing the inductive step, in the case where positions 2n + 1 and 2n + 2 are both chosen.  (Hint: Look at positions n + 1 and 2n + 2. Argue that we can’t use both of them, but that if we use one of them, it doesn’t matter which.) Since n + 1 divides 2n + 2, using both would violate the rule.  But no other number in {1, . . . , 2n + 2} divides n + 1 or 2n + 2. So if we legally used 2n + 2, and we substituted n + 1 for 2n + 2, we would also be legal.  But then we would have a solution in the previous case, which we have proved to be impossible.

Question 3 (35):  Let Σ = {0, 1} and let R be the regular expression (01 + 10)* .

(a, 10)  Construct a λ-NFA N such that L(N) = L(R). For full credit, use the construction from the textbook and lecture.

State 1 is the start state, and state 6 is the only final state. We build an ordinary NFA for (01 + 10) with states 2, 3, 4, and 5, with the transitions (2 , 0, 3), (2, 1, 4), (3, 1, 5), and (4, 0, 5). Then we implement the star construction and add λ-moves from 1 2, from 2 to 5, from 5 to 2, and from 5 to 6.

(b, 10)  Using the given construction from the textbook and lecture, build an ordinary NFA N′  such that L(N′ ) = L(N).

We use the same state set, and 1 becomes a second final state.  Each of the four letter moves in N leads to three letter moves in N′ : (2, 0, 3) creates itself, (1, 0, 3) and (5, 0, 3), (2, 1, 4) creates itself, (1, 1, 4) and (5, 1, 4), (3, 1, 5) creates itself, (3, 1, 2) and (3, 1, 6, and (4, 0, 5) creates itself, (4, 0, 2) and (4, 0, 6).

(c, 10) Using the Subset Construction, build a DFA D such that L(D) = L(N′ ).

The start state, which is final, is {1}.  We have δ({1}) = {3} and δ({1}, 1) = {4}.  We need a new final state f = {2, 5, 6}, because the 1-move from {3} and the 0-move from {4} both go there. The other moves from {3} and {4} go to a death state, which has both moves to itself. Then δ(f, 0) = {3} and delta(f, 1) = {4}, and we finish the construction with five states.

(d, 5)  Using the minimization construction, or otherwise if you can justify your result, find a minimal DFA M such that L(M) = L(D).

The three non-final states must all be separated, but the two final states may be merged to give four states.  State {3} goes to non-final on 0 and final on 1, state {4} goes to final on 0 and non-final on 1, and the death state goes to non-final either way. After we break the class of non-final states into three classes, we still find that both final states go to {3} on 0 and to {4} on 1, so they can be merged.

Question 4 (30):  The following are fifteen true/false questions, with no explanation needed or wanted, no partial credit for wrong answers, and no penalty for guessing. Some of them refer to the scenarios of the other problems, and/or the entities defined on the supplemental sheet.

●  (a) Let p be any position for the Toads and Frogs game, with Toad’s turn to start. Then if Toad does not have a winning strategy from position p, then Frog does have a winning strategy from p.

TRUE. This follows from the Determinacy Theorem.

●  (b) If L is not a regular language, and L′  is some language such that L′  C L, then L′

must not be a regular language.

FALSE. L′  might be empty.

●  (c) Consider a BFS and a DFS search of the same finite state space, with both searches using a closed list so that the nodes that have been visited are not added to the open

list again. Then BFS will find all reachable states, but DFS might not. FALSE. Both BFS and DFS find all reachable states.

●  (d) Let L be a regular language, and let L′  be a language made by removing no more than 17 strings from L. Then L′  is also a regular language.

TRUE. We could build a DFA for L, build a second DFA that accepts every string except for the excluded strings, then build a third DFA whose language is the intersection of the first two, and this language is L′ .

●  (e) If L is any regular language, then there exists some Turing machine that decides L. TRUE. A TM can simulate a DFA.

●  (f) Let P (w) be a predicate ranging over the strings Σ* , where Σ = {a, b}.  If P (λ) is

true, and Vw : P (w) → (P (wa) A P (wb)), then Vw : P (w) is true.

TRUE. This is the standard definition of string induction.

●  (g) The language {an bn  : n ≥ 0} is Turing recognizable but not Turing decidable. FALSE. It is decidable, using the TM that we built in Lecture 37.

●  (h) Let SC be the set of partially completed 3 × 3 Sudoku positions (encoded as strings over the alphabet {1, 2, 3, 4, 5, 6, 7, 8, 9, x} where an x is not yet filled in) that can be

legally completed. Then the language SC is not regular.

FALSE. Every finite language is regular.

●  (i) The language SC of the preceding problem is Turing decidable. TRUE. Every finite language is Turing decidable.

●  (j) The relation S from Question 1 is not a partial order, but if we define a relation S′ so that S′ (x, y) 4 (S(x, y) V (x = y)), then S′  is a partial order.

TRUE. It was already antisymmetric and transitive, and this change makes is reflexive instead of antireflexive.

●  (k) If u is a string in a language L, and v is a string such that u and v are L-equivalent as in the Myhill-Nerode Theorem, then v must also be in L.