1. Pattern Matching [Online] (15 points) Use the method given in class to design a DFA to determine all occurrences of the string 11011011001 in strings over the alphabet f0; 1g. You must submit and check your answers to this question using https://grinch.cs.washington.edu/cse311/fsm. 2. Diagonalization (20 points) Let B be the set of all infinite binary sequences that are 1 in odd positions, i.e., any string in B is of the form 1 ∗ 1 ∗ 1 ∗ 1 ∗ : : : where we can have 0 or a 1 instead of each ∗. Show that B is uncountable using a proof by diagonalization. 3. Countability (20 points) Complex numbers can be written as a + bi where a; b are real numbers and i is the square root of −1. Show that subset R of complex numbers given by R = fa + bi : a; b are rationalg is countable 4. Irregularity (30 points) Using the method shown in class prove that that the following languages are not regular. (a) [15 Points] The set of binary strings of the form f0n1m0n : m < ng. (b) [15 Points] The set of strings 0n where n is a perfect square, i.e., n = k2 for some k 2 N. 5. Undecidability (15 points) Consider the set Prime = f(CODE(P); x) : P reads x and halts if and only if x is a primeg Show that Prime is undecidable using the fact that the Halting Problem is undecidable. 1
