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.

Course Link: Click Here


Theory of Computation Week 7 Nptel Assignment Answers
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

See also  Theory of Computation | Week 1

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

All Weeks of Theory of Computation: Click here

For answers to additional Nptel courses, please refer to this link: NPTEL Assignment Answers