CS 3800

Homework 3

Spring 2024

1. [6 Points] In the shortlex numbering of strings over the alphabet {0, 1, 2, 3} what number corre-sponds to string 0 0 2 1 3 0 2 ?

2. [10 Points] In the shortlex numbering of strings over the alphabet {a, b, c}, what string has number 28599 ?

3. [8 Points] Suppose that S0, S1, S2, . . . is a sequence of subsets of N. Which one of the following sets is guaranteed to be different from all sets in the sequence?

(a) S = {n | n ̸∈ Sn2 }

(b) S = {n | n 2 ̸∈ Sn2 }

(c) S = {n 2 | n ̸∈ Sn2 }

(d) S = {n 2 | n 2 ̸∈ Sn}

(e) S = {n 2 | n ̸∈ Sn}

Explain why your chosen set is guaranteed not to be in the sequence S0, S1, S2, . . .

4. [9 Points] Use (a modified) diagonalization to show that for each sequence S0, S1, S2, . . . of subsets of N, there is a set S ⊆ N consisting only of even numbers such that

S ≠ S0, S1, S2, . . .

Give a formula for your set S, similar to those suggested in Problem 3.

5. [4 Points] Alice and Bob. Alice found a proof that no numbering of finite subsets of N is possible, that includes every finite subset of N; that is, for each sequence S0, S1, S2, . . . of finite subsets of N, there is some finite subset S ⊆ N that isn’t in the sequence. Here is her argument:

Consider any sequence S0, S1, S2, . . . of finite subsets of N.

1. Claim: some finite subset of N is not in the sequence.

2. Proof of the claim:

3. Define a new subset S ⊆ N by:

S = {n ∈ N | n ̸∈ Sn}

4. Thus for each n ∈ N, number n guarantees that S ≠ Sn

5. Therefore S is not a set of the sequence. □

Bob claims that there is an error in Alice’s argument. Is he right? If yes, what is the flaw? If no, does Alice’s result contradict our results in lecture?

6. [5 Points] Cantor’s Theorem states that for every function f : X → P(X) from a set X to its power set, there exists a set S ⊆ X such that S ≠ f(x) for all x ∈ X. This set S is constructed using Cantor’s diagonalization method.

Suppose that X = {a, b, c, d, e} and that f is given by

f(a) = {a, c, d, e}

f(b) = {a, d, e}

f(c) = ∅

f(d) = {a, c, d}

f(e) = {a, b, d}

What is the set S constructed by Cantor’s diagonalization method?

7. [9 Points] Consider the finite automaton whose diagram is depicted below.

(a) Describe the language recognized by this automaton.

(b) Write down this automaton’s formal (5-tuple) description. (Specify each of the 5 compo-nents.)

8. [5 Points] Draw the state transition diagram for the DFA whose formal description is

({q1, q2, q3}, {a, b}, δ, q1, {q1, q2})

where δ is the function given in the following table:

9. [6 Points]. Tint. Submission is separate from the other problems. Instructions will be posted on Piazza. Let language L consist of all binary strings in which any two successive zeros are separated by an even number of ones. For example, ε ∈ L and 101101 ∈ L and 101100111101 ∈ L but 010 ̸∈ L and 1011011101 ̸∈ L. Write a tint program for a DFA over the alphabet {0, 1} such that L is the language accepted by your DFA.

10. [0 Point] Do not submit. Exercise 1.1 page 83. The solution is in the book page 94, this is for practice only.

11. [0 Point] Do not submit. Exercise 1.2 page 83. The solution is in the book page 94, this is for practice only.