5. [30pt; 10pt each] State and prove whether the following languages have any of these properties (recall that they could have more than one): DEC: Decidable TR: Turing Recognizable co-TR: co-Turing recognizable NTR: not Turing recognizable NcoTR: not co-Turing recognizable La = {(M) I M is a TM and M accepts some string w which has 000 as a suffix) iff there exists Recall that string y E 0,1) is a suffix of string w E 0,1 some e (0, 1 such that w- L,-M) I M is a TM and IL(M)| 2) Recall that L(M) is the size of the language, which is the number of the accepted strings by M. e-KMi, M2) Mi,M2 are TMs and abc E L(Mi)UL(M2)) Hint: You may want to reduce ATM to La, Lb, and Lc. In this case you may want to construct the following TM internally given the description of M and input w in your proofs (similar to the proof of the undecidability of ETM): NM-On input 1. Run M on w: 2. if M accepts w, accept z." 5. [30pt; 10pt each] State and prove whether the following languages have any of these properties (recall that they could have more than one): DEC: Decidable TR: Turing Recognizable co-TR: co-Turing recognizable NTR: not Turing recognizable NcoTR: not co-Turing recognizable La = {(M) I M is a TM and M accepts some string w which has 000 as a suffix) iff there exists Recall that string y E 0,1) is a suffix of string w E 0,1 some e (0, 1 such that w- L,-M) I M is a TM and IL(M)| 2) Recall that L(M) is the size of the language, which is the number of the accepted strings by M. e-KMi, M2) Mi,M2 are TMs and abc E L(Mi)UL(M2)) Hint: You may want to reduce ATM to La, Lb, and Lc. In this case you may want to construct the following TM internally given the description of M and input w in your proofs (similar to the proof of the undecidability of ETM): NM-On input 1. Run M on w: 2. if M accepts w, accept z