Theory of Computation Week 7 Nptel Assignment Answers
Are you looking for Theory of Computation Week 7 Nptel Assignment Answers? You’ve come to the right place! Access the latest and most accurate solutions for your Assignment 7 in the Theory of Computation course. Our detailed answers are designed to help you understand key concepts and excel in your studies.
Theory of Computation Week 7 Nptel Assignment Answers
Theory of Computation Week 7 Nptel Assignment Answers (July-Dec 2024)
1. The union of two decidable languages is:
A) Context-free but not necessarily regular B) Regular C) Decidable but not necessarily context-free D) Recognizable but not necessarily decidable
Answer: C) Decidable but not necessarily context-free
2. Which of the following languages is not Turing-recognizable?
A) {⟨R⟩∣R is an RE and L(R)=∅} B) {⟨M⟩∣M is a NFA and L(M)=∅} C) {⟨G⟩∣G is a CFG and L(G)=∅} D) {⟨M⟩∣M is a TM and L(M)=∅}
Answer: D) {⟨M⟩∣M is a TM and L(M)=∅}
3. Consider the language L={⟨G1,G2⟩∣G1,G2 are CFGs and L(G1)=L(G2)}. Then L is:
A) Regular B) Decidable but not regular C) Turing recognizable but not decidable D) Not Turing recognizable
Answer: B) Decidable but not regular
4. The intersection of two Turing-recognizable languages is:
A) Context-free but not necessarily regular B) Regular C) Decidable but not necessarily context-free D) Recognizable but not necessarily decidable
Answer: D) Recognizable but not necessarily decidable
5. What can we say about the following two languages?
ATM = {⟨M,w⟩∣M is a TM that accepts the string w} ETM = {⟨M⟩∣M is a TM and L(M)=∅}
A) ATM is Turing recognizable, ETM is Turing recognizable B) ATM is co-Turing recognizable, ETM is Turing recognizable C) ATM is Turing recognizable, ETM is co-Turing recognizable D) ATM is co-Turing recognizable, ETM is co-Turing recognizable
Answer: D) ATM is co-Turing recognizable, ETM is co-Turing recognizable
6. Consider the following languages:
L1 = {⟨L⟩∣L is a regular language such that |L|=10} L2 = {⟨L⟩∣L is a regular language such that |L| is infinity}
Which of the following statement is true?
A) L1 and L2 both are undecidable B) L1 and L2 both are decidable C) L1 is decidable but L2 is undecidable D) L1 is undecidable but L2 is decidable
Answer: B) L1 and L2 both are decidable
7. Which of the following statements is false?
A) Complement of a regular language is also regular B) Complement of a DCFL is also a DCFL C) Complement of a decidable language is also decidable D) Complement of a Turing-recognizable language is also Turing recognizable
Answer: D) Complement of a Turing-recognizable language is also Turing recognizable
8. Consider the language L={⟨D1,D2⟩∣D1,D2 are DFAs and L(D1)=L(D2)}. Then L is:
A) Regular B) Decidable but not regular C) Turing recognizable but not decidable D) Not Turing recognizable
Answer: B) Decidable but not regular
These are Theory of Computation Week 7 Nptel Assignment Answers
