## 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_{1},G_{2}⟩∣G_{1},G_{2} are CFGs and L(G_{1})=L(G_{2})}

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_{1}={⟨L⟩∣L is a regular language such that |*L*|=10}

L_{2}={⟨L⟩∣L is a regular language such that |*L*| is infinity}

Which of the following statement is true?

- L
_{1}and L_{2}both are undecidable - L
_{1}and L_{2}both are decidable - L
_{1}is decidable but L_{2}is undecidable - L
_{1}is undecidable but L_{2}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_{1},D_{2}⟩∣D_{1},D_{2} are DFAs and L(D_{1})=L(D_{2})}

Then L is

- regular.
- decidable but not regular.
- Turing recognizable but not decidable.
- not Turing recognizable.

Answer :-For Answers Click Here