CS3331 – Assignment 4 due Dec. 6, 2020, (latest to submit: Dec. 9, 11:55pm) NOTE: The 48h extension due to self-reporting will be included, for this assignment only, in the no-penalty 3-day extension....

This is my assignment for theory of computation course, there are 2 questions


CS3331 – Assignment 4 due Dec. 6, 2020, (latest to submit: Dec. 9, 11:55pm) NOTE: The 48h extension due to self-reporting will be included, for this assignment only, in the no-penalty 3-day extension. That means the self reporting assignments must be submitted also before Dec. 9, 11:55pm. That is because I want to be able to post the solutions for the assignment a few days before the final exam. 1. (70pt) For each of the following languages, prove, without using Rice’s Theorem, whether it is (i) in D, (ii) in SD but not in D, or (iii) not in SD. 1 L1 = {| M accepts at most two single-letter strings} 2 L2 = {| M accepts no even-length strings} 3 L3 = {| M accepts infinitely many strings that start with a} 4 L4 = {| M accepts at least five palindrome strings} 5 L5 = {| there exists an SD language L such that M accepts precisely the strings in L} 6 L6 = {| there is no 2-tape TM M ′ with L(M) = L(M ′)} 7 L7 = {| there is a deciding TM M ′ such that L(M) = ¬L(M ′)} 2. (30pt) For each of the languages in question 1, indicate whether Rice’s Theorem can be used or not to prove that the corresponding language is not in D. Explain why. READ ME! Submit your solution as a single pdf file on owl.uwo.ca. Solutions should be either typed or legibly handwritten. Make sure you submit everything as a single pdf file. 1