# Theory of Computation Week 3 Nptel Assignment Answers

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

**Q1. **Let L be a regular language. Then according to the pumping lemma for regular languages, there exists an integer p≥1 such that every string w∈L can be written as w=xyz satisfying the following conditions:

∣y∣≥1

∣xy∣≤p

and

**∀n≥0,xynz∈L**

∃n≥0,xynz∈L

∀n≥0,xyzn∈L

∃n≥0,xnyz∈L

**Answer: ∀n≥0,xynz∈L**

**Q2.Which states are equivalent in the following DFA?**

q0 and q1 only

**q1 and q2 only**

q0 and q2 only

q0,q1 and q2

**Answer: q1 and q2 only**

**For answers or latest updates join our telegram channel: Click here to join **

**These are Theory of Computation Week 3 Nptel Assignment Answers**

**Q3. **Which of the following is a regular language?

{0m1m|m>0 is a natural number}

**{0m1n|m,n>0 are natural numbers}**

{0m1m|m≥0 is a natural number}

{0m1n|m,n≥0 are natural numbers such that m≥n}

**Answer: {0m1n|m,n>0 are natural numbers}**

**Q4. **Which of the following is not a regular language?

{0m|m is a natural number}

{02m|m is a natural number}

**{03m+2|m is a natural numberm≥n}**

{0m2|m is a natural number}

**Answer: {03m+2|m is a natural numberm≥n}**

**For answers or latest updates join our telegram channel: Click here to join **

**These are Theory of Computation Week 3 Nptel Assignment Answers**

**Q5. **Which of the following statements is not true?

Any regular language satisfies the pumping lemma.

Any language that does not satisfy the pumping lemma cannot be regular.**Any language that satisfies the pumping lemma must be regular.**

A language that is not regular may also satisfy the pumping lemma.

**Answer: Any language that satisfies the pumping lemma must be regular.**

**Q6. **Which of the following languages is not regular?

**{0n∣n is prime}**

{0i1j∣i,j≥0}

Set of binary strings where every occurrence of 1 is followed by 0

Set of binary strings such that the numbers represented by them in binary representation is divisible by 3

**Answer: {0n∣n is prime}**

**For answers or latest updates join our telegram channel: Click here to join **

**These are Theory of Computation Week 3 Nptel Assignment Answers**

**Q7. **How many states are there in the minmal DFA corresponding to the following DFA?

3

4

6**8**

**Answer: 8**

**Q8. **How many final/accepting states are there in the minmal DFA corresponding to the following DFA?

1

2**3**

4

**Answer: 3**

**For answers or latest updates join our telegram channel: Click here to join **

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