Homework 9 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 {0,1}. 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 = {a + bi : a,b are rational} 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 {0n1m0n : m < n}. (b) [15 Points] The set of strings 0n where n is a perfect square, i.e., n = k2 for some k ∈N. 5. Undecidability (15 points) Consider the set Prime = {(CODE(P),x) : P reads x and halts if and only if x is a prime} Show that Prime is undecidable using the fact that the Halting Problem is undecidable. 1
