NPTEL Theory of Computation Week 7 Assignment Answers 2024

NPTEL Theory of Computation Week 7 Assignment Answers 2024

1. The union of two decidable languages is

• context-free but not necessarily regular
• regular
• decidable but not necessarily context-free
• recognizable but not necessarily decidable

Answer :- For Answers Click Here 

2. Which of the following languages is not Turing-recognizable?

• {⟨R⟩∣R is an RE and L(R)=∅}
• {⟨M⟩∣M is a NFA and L(M)=∅}
• {⟨G⟩∣G is a CFG and L(G)=∅}
• {⟨M⟩∣M is a TM and L(M)=∅}

Answer :- For Answers Click Here 

3. Consider the language
L={⟨G₁,G₂⟩∣G₁,G₂ are CFGs and L(G₁)=L(G₂)}

Then L is

• regular.
• decidable but not regular.
• Turing recognizable but not decidable.
• not Turing recognizable.

Answer :- 

4. The intersection of two Turing-recognizable languages is

• context-free but not necessarily regular
• regular
• decidable but not necessarily context-free
• recognizable but not necessarily decidable

Answer :- 

5. What can we say about the following two languages?

A_TM={⟨M,w⟩∣M is a TM that accepts the string w}
E_TM={⟨M⟩∣M is a TM and L(M)=∅}

• A_TM is Turing recognizable, E_TM is Turing recognizable
• A_TM is co-Turing recognizable, E_TM is Turing recognizable
• A_TM is Turing recognizable, E_TM is co-Turing recognizable
• A_TM is co-Turing recognizable, E_TM is co-Turing recognizable

Answer :- 

6. Consider the following languages
L₁={⟨L⟩∣L is a regular language such that |L|=10}
L₂={⟨L⟩∣L is a regular language such that |L| is infinity}

Which of the following statement is true?

• L₁ and L₂ both are undecidable
• L₁ and L₂ both are decidable
• L₁ is decidable but L₂ is undecidable
• L₁ is undecidable but L₂ is decidable

Answer :- For Answers Click Here 

7. Which of the following statements is false?

• Complement of a regular language is also regular
• Complement of a DCFL is also a DCFL
• Complement of a decidable language is also decidable
• Complement of a Turing-recognizable language is also Turing recognizable

Answer :- 

8. Consider the language
L={⟨D₁,D₂⟩∣D₁,D₂ are DFAs and L(D₁)=L(D₂)}

Then L is

• regular.
• decidable but not regular.
• Turing recognizable but not decidable.
• not Turing recognizable.

Answer :- For Answers Click Here