CS3331 – Assignment 4 due Dec. 6, 2021 2-day no-penalty extension until: Dec. 8, 11:55pm (SRA’s cannot be used to extend further) 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 = {
| L(M) ⊆ {a, aa}} (2) L2 = {| L(M) ⊇ {a, aa}} (3) L3 = {| L(M) = {a, aa}} (4) L4 = {| L(M) ∈ D} (5) L5 = {| ¬L(M) ∈ D} (6) L6 = {| L(M) ∈ SD} (7) L7 = {| ¬L(M) ∈ SD} (8) L8 = {| there exists some input w on which M performs at least one right move}. (9) L9 = {| there exists some input w which M accepts in |w| steps or less}. (10) L10 = {| ε ∈ L(M1) ∩ L(M2)}. 2. (30pt) For each of the languages in question 1 which is not in D, explain briefly how you would use Rice’s Theorem to prove they are not in D. READ ME! Submit your solution as a single pdf file on owl.uwo.ca. Solutions should be typed but high-quality hand-written solutions are acceptable. Make sure you submit everything as a single pdf file. LATEX: For those interested, the best program for scientific writing is LATEX. It is far superior to all the other programs, it is free, and you can start using it in minutes; here is an introduction: https://tobi.oetiker.ch/lshort/lshort.pdf 1 欢迎咨询51作业君
