Computer Science 4602, Fall 2019
Assignment 1

1. Write each of the following using set notation.

   1. The set that contains only string aab
   2. The set containing only the empty string
   3. The empty set
   4. The set containing all natural numbers that are greater than 10
   5. The set containing all strings over alphabet {a, b}

2. 1. What is {1, 3, 5, 6} ∪ {2, 3, 5, 9}?
   2. What is {1, 3, 5, 6} ∩ {2, 3, 5, 9}?
   3. What is {1, 3, 5, 6} − {2, 3, 5, 9}?
   4. What is |{ab, bbb}|?
   5. What is |{ε, a, b}|?
   6. Is ε ∈ {}?
   7. Is {} ∈ {}?
   8. Is {} ⊆ {}?
   9. Is {ε} ⊆ {}?
   10. Is {} ⊆ {ε}?

3. Is {} ∪ S = S for every set S? Justify your answer.

4. Briefly define the following.

   1. What is the definition of an alphabet?
   2. What is the definition of a string over alphabet Σ?
   3. What is the definition of a language?

5. Explain the error in the following proof that 1 = 2.

   Consider equation a = b. Multiply both sides by a, obtaining a² = ab. Subtract b² from both sides to get a² − b² = ab − b². Factor each side, giving (a + b)(a − b) = b(a − b). Divide each side by (a − b), giving a + b = b. Now choose a = 1 and b = 1, giving 2 = 1.

6. Prove that, in every simple graph with at least two vertices, there are two vertices that have the same degree.

7. A number is rational if it is the ratio of two integers. Prove that √2 is not rational. (Hint. Reason by contradiction. Suppose that there exist two integers x and y so that x/y = √2. Square both sides. Think about prime factorizations of integers. Two positive integers are equal if and only if they have the same prime factorization.

8. Draw a transition diagram of a DFA that accepts exactly each of the following languages over alphabet Σ = {a, b, c}.

   1. {w ∈ Σ^* | w begins with a and ends with b}
   2. {w ∈ Σ^* | w has at least three c's}
   3. {w ∈ Σ^* | w has aab as a contiguous substring}
   4. {w ∈ Σ^* | w does not have aab as a contiguous substring}
   5. {w ∈ Σ^* | w is any string except ab and bba}
   6. {w ∈ Σ^* | w ends with cc}

9. Show that each of the following languages is not regular. Do not use the Pumping Lemma. a^k is a string of exactly k a's.

   1. {www | w ∈ {a, b, c}^*} (That is, any string written three times in a row.)
   2. {a^k | k is a power of 2}
   3. {aⁱb^jc^{i + j} | i > 0, j > 0, k > 0}