Assignment 4 Solution

(80pt) 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.



L1 = f<Mj f"; ab; ababg L(M)g



2 L2 = f<Mj L(M) \ (ab) is in niteg 3 L3 = f<Mj L(M) \ (ab) is niteg 4 L4 = f<Mj L(M) \ (ab) = ;g




5 L5 = f<Mj L(M) \ (ab) 6= ;g




6 L6 = f<Mj L(M) 6= L(M0) for any other TM M0g 7 L7 = f<M j :L(M) 2 Dg.

8 L8 = f<M j L(M) 2 SDg.




(20pt) 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.



Note Submit your solution as a pdf le on owl.uwo.ca.













































































































1