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

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