1. (80pt) For each of the following languages, prove, without using Rice's Theorem, whether it is...

 

Transcribed Image Text:

1. (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. 1 L = { | {, ab, abab} CL(M)} 2 L2 = { | L(M) 3 L3 = { | L(M) (ab)* is infinite} (ab)* is finite} 4 L = { | L(M) n (ab)* = 0} 5 L5 = { |L(M) n (ab)* 0} 6 L6 = { | L(M) L(M') for any other TM M'} 7 L7 = { |L(M) D}. 8 L8 = { | L(M) SD}. 2. (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. 1. (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. 1 L = { | {, ab, abab} CL(M)} 2 L2 = { | L(M) 3 L3 = { | L(M) (ab)* is infinite} (ab)* is finite} 4 L = { | L(M) n (ab)* = 0} 5 L5 = { |L(M) n (ab)* 0} 6 L6 = { | L(M) L(M') for any other TM M'} 7 L7 = { |L(M) D}. 8 L8 = { | L(M) SD}. 2. (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.