[SOLVED] CS3331 Assignment 4 2018 Decidable and Semi-Decidable Languages II

CS3331 Assignment 4 2018 Decidable and Semi-Decidable Languages II
Due: Monday, Dec 3, 2018 (Latest to submit: Thursday, Dec 6)
1. (20pt) Is the set SD closed under intersection? Prove your answer. Clear English description of any Turing machines is sufficient. (That is, you dont have to effectively build the machine, instead explain how the machine behaves.)
2. (20pt)IfL1 andL3 areinDandL1 L2 L3 ,whatcanwesayaboutwhetherL2 isinD?
3. (50pt) For each of the following languages, prove, without using Rices Theorem, whether it is (i) in D or
(ii) in SD but not in D.
(a) L1 = {< M >: a L(M) and b L(M)}.
(b) L2 = {< M,w >: M, on input w, never writes on its tape}.
(c) L3 = {< M,n >: M accepts at least one string of length > n}. (d) L4 = {< M >: L(M) = L(M0) for any other TM M0}
(e) L5 = {< M,w >: TM M accepts w and rejects wR}.
4. (10pt) Prove using reduction from H = {< M > : TM M does not halt on input w} that the language
HANY = {< M > : there does not exist a string on which TM M halts} is not in SD. (Hint: see pp. 476-77 in the textbook).
Note well: You may submit your assignment in one of two ways:
Ideally, submit your solution as a pdf file on OWL (scanned written assignments are fine). Assignments
submitted this way will not be accepted after 11:59 pm on December 6.
Otherwise staple your assignment and hand in solutions in class or to the 3331 dropbox (locker #306, across from the elevator on the 3rd floor of Middlesex College). Assignments submitted this way will not be accepted after 5:00 pm on December 6.