# Theory of Computation Week 6 Nptel Assignment Answers

Are you looking for Theory of Computation Week 6 Nptel Assignment Answers? You’ve come to the right place! Access the latest and most accurate solutions for your Assignment 6 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**

## Table of Contents

**Theory of Computation Week 6 Nptel Assignment Answers (July-Dec 2024)**

**1. Consider the following languages L1 = {anbnam ∣ n,m≥0} and L2 = {anbman ∣ n,m≥0}. Which of the following languages is DCFL?**

A) L1¯¯¯¯¯¯

B) L1∩L2

C) L1∪L2

D) L1∩L2¯¯¯¯¯¯

**Answer:** D) L1∩L2¯¯¯¯¯¯

**2. Which of the following languages is not necessarily context-free?**

A) Complement of a DCFL

B) Intersection of a DCFL and a regular language

C) Union of two DCFLs

D) Intersection of two DCFLs

**Answer:** A) Complement of a DCFL

**3. Which of the following languages is necessarily deterministic context-free?**

A) Complement of a DCFL

B) Intersection of a DCFL and a regular language

C) Union of two DCFLs

D) Intersection of two DCFLs

**Answer:** D) Intersection of two DCFLs

**4. Let L1 and L2 be two languages such that L1⊆L2. Consider the following statements: S1: If L1 is DCFL then L2 is also DCFL S2: If L2 is DCFL then L1 is also DCFL S3: Either both L1 and L2 are DCFL or neither L1 nor L2 is DCFL Which of the following is correct?**

A) S1 is true

B) S2 is true

C) S3 is true

D) None of S1, S2, S3 is true

**Answer:** B) S2 is true

**5. Let L1 be a context-free language, L2 be a DCFL. Which of the following is not true?**

A) L1¯¯¯¯¯¯∪L2 is necessarily context-free

B) L1∪L2¯¯¯¯¯¯ is necessarily context-free

C) L1⋅L2¯¯¯¯¯¯ is necessarily context-free

D) L1∪L2 is necessarily context-free

**Answer:** B) L1∪L2¯¯¯¯¯¯ is necessarily context-free

**6. Which of the following statements is not true about a deterministic Turing Machine?**

A) Equivalent to a nondeterministic Turing Machine in terms of computability

B) Can go to multiple configurations from a given configuration

C) Can have multiple accept configurations

D) Accepts a decidable language

**Answer:** B) Can go to multiple configurations from a given configuration

**7. Which of the following is a deterministic context-free language?**

A) {wwR∣w∈{0,1}∗ and wR is the reverse of w}

B) {ww∣w∈{0,1}∗}

C) {w∣w∈{0,1}∗ and w has equal number of 0’s and 1’s}

D) {anbncm or anbmcn∣m,n are natural numbers}

**Answer:** A) {wwR∣w∈{0,1}∗ and wR is the reverse of w}

**8. Which of the following statements is not true about a Turing Machine?**

A) Can move across the work tape in both directions

B) Can write on the work tape

C) Has a fixed (independent of the input) number of states

D) Has a fixed (independent of the input) number of configurations

**Answer:** D) Has a fixed (independent of the input) number of configurations

These are Theory of Computation Week 6 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