Problem 1 (20 points) Consider the set of all functions from the natural numbers to the set {a, b, c}. Show that this set is uncountable by using a diagonalization argument. Problem 2 (25 points) Let...

Work on all assignment in 24hours, do not copy online source


Problem 1 (20 points) Consider the set of all functions from the natural numbers to the set {a, b, c}. Show that this set is uncountable by using a diagonalization argument. Problem 2 (25 points) Let Σ be an alphabet such that {a, b} ⊆ Σ and let L1 be the language {〈M〉 | M is a DFA such that L(M) ⊆ Σ∗ and L(M) contains at least one string with an equal number of as and bs}. Prove that L1 is decidable. Hint: Theorems about context-free languages should be useful in doing this problem. Problem 3 (25 points) Assume an alphabet that contains the letters a and b and let L2 be the language {〈M〉 | M is a Turing machine such that L(M) contains at least one string with an equal number of as and bs}. Use Rice’s theorem to show that L2 is undecidable. You must use Rice’s theorem for credit in this problem. Problem 4 (8 + 14 + 8 points) An (undirected) graph G is k-colorable if we can color the nodes in the graph using at most k colors in such a way that no two adjacent nodes have the same color. For each number k, we can then define a collection of languages that correspond to the descriptions of graphs that are k-colorable as follows: Color(k) = {〈G〉 | G is an undirected graph that is k-colorable} This problem requires you to show that Color(3) ≤P Color(k) for any k ≥ 3. We will do this in the following steps: 1. Describe a polynomial time reduction from Color(3) to Color(k) for k ≥ 3. Note that while you will show that what you describe is a polynomial time reduction only in the next two steps, you will not get credit for this part if it does not have the desired properties. Hint: Think of modifying the given graph by adding some new nodes and edges from them. 2. Show that what you have described is in fact a reduction. In particular, you have to show that the graph it produces is in Color(k) if and only if the original graph is in Color(3). 3. Show that your reduction can be carried out in a number of steps that is polynomial in the size of the input. 2