Question

13. (1 point) Which of the following statement could be false where Lį and L2 are decidable lan- guages? A. Li · L2 is decidable. B. Li Lis undecidable. C. Lin L2 is decidable. D. LI U L2 is decidable. E. None of the above. 14. (1 point) Which of the following statement could be false where Lj is decidable and L2 is recognizable? A. Li · L2 is recognizable. B. Li · L2 is decidable. C. Lin L2 is recognizable. D. LI U L2 is recognizable. E. None of the above. 15. (1 point) Which of the following statements could be false? A. If there exists an enumerator to enumerate L, then L is recognizable. B. If an enumerator enumerates L, then L is decidable. C. If L is recognizable, then there exists an enumerator that enumerates L. D. If L is decidable, then there exists an enumerator that enumerates strings in L in the natural string ordering. E. None of the above.

Answer 1

Answering the first Question 13. :

Correct Answer :

None of the above

Reason :

1. The decidable languages are recognized by the Turning Machine. These languages are closed under union, intersection, Kleene closure and the complement.
2. Therefore, when L1 and L2 are decidable languages, then

• L1.L2 is also a decidable language.
• (L1*)'(L2*)' is also decidable languages.
• (L1') $\tiny \bigcap$ L2 is also a decidable language.
• ((L1 ') U L2)' is also decidable languages.