Q1 (6 points) a. Explain why decidable languages are closed under complementation. Consider that L1 is...

Transcribed Image Text:

Q1 (6 points) a. Explain why decidable languages are closed under complementation. Consider that L1 is a decidable language and let M1 be a Turing Machine that decides L1. How can we construct a Turing Machine that decides complement of L1? b. Explain why Turing recognizable languages are not closed under complementation. Consider that L2 is a Turing Recognizable language and let M2 be a Turing Machine that recognizes L2. Why is it not possible to construct a Turing Machine that recognizes complement of L2? c. Explain why decidable languages are closed under union and intersection. Consider that L3 and L4 are decidable languages and let M3 and M4 be Turing Machines that decide L3 and L4, respectively. How can we construct Turing Machines that decide L3 U L4 and L3 n 14, respectively? d. Explain why Turing recognizable languages are closed under union and intersection. Consider that L5 and L6 are Turing Recognizable languages and let M5 and M6 be Turing Machines that recognize L5 and L6, respectively. How can we construct Turing Machines that recognize L5 U L6 and L5 N L6, respectively? Q1 (6 points) a. Explain why decidable languages are closed under complementation. Consider that L1 is a decidable language and let M1 be a Turing Machine that decides L1. How can we construct a Turing Machine that decides complement of L1? b. Explain why Turing recognizable languages are not closed under complementation. Consider that L2 is a Turing Recognizable language and let M2 be a Turing Machine that recognizes L2. Why is it not possible to construct a Turing Machine that recognizes complement of L2? c. Explain why decidable languages are closed under union and intersection. Consider that L3 and L4 are decidable languages and let M3 and M4 be Turing Machines that decide L3 and L4, respectively. How can we construct Turing Machines that decide L3 U L4 and L3 n 14, respectively? d. Explain why Turing recognizable languages are closed under union and intersection. Consider that L5 and L6 are Turing Recognizable languages and let M5 and M6 be Turing Machines that recognize L5 and L6, respectively. How can we construct Turing Machines that recognize L5 U L6 and L5 N L6, respectively?

Answer rating: 100% (QA)

Question a To construct a machine that decides the complementation of L1 we simulate the Turning Mac... View the full answer