SOLVED COMP 335 Introduction to Theoretical Computer Science Assignment 6

  1. [30 Points] Classify the following languages into one of the three categories a) regular, b) context-free but not regular, and c) not context-free. Prove your answer. (a) L1 = {a i b j c k | k = i × j and 0 < i < 10 < j} (b) L2 = {xyz | x, y, z ∈ {a, b} ⋆ and na(x) = nb(z)} (c) L3 = {wuwR | w, u ∈ {a, b} ⋆ and |w| = |u|} Note that in order to show that a language is context-free but not regular, you need to prove both that it is context-free and also that it is not regular. 2. [10 Points] Give a Turing machine for L = {a}·{a, b} + that does not halt on rejection. 3. [20 Points] Give a Turing machine for each of the following languages: (a) L1 = {a n b mc k | m ≥ n, k ≥ 1}. (b) L2 = {xy | x ∈ {a, b} +, y ∈ {c} + and na(x) = nc(y)}. 4. [20 Points] Draw transition diagrams for Turing machines that compute the following functions. In each case, give a brief description in English of your solution strategy. (a) f(1n ) = 12n (b) f(1n ) = 1n 2