Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

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