# Theory of Computation Week 2 Nptel Assignment Answers

Are you looking for Theory of Computation Week 2 Nptel Assignment Answers? You’ve come to the right place! Access the latest and most accurate solutions for your Assignment 2 in the Theory of Computation course. Our detailed answers are designed to help you understand key concepts and excel in your studies.

## Theory of Computation Week 2 Nptel Assignment Answers

Session: JULY-DEC 2024

Q1. Which of the following is equivalent to the set described by the regular expression 11∗00∗ ?

{1m0m|m>0 is a natural number}

{1m0n|m,n>0 are natural numbers}

{1m0m|m≥0 is a natural number}

{1m0n|m,n≥0 are natural numbers}

Answer: Updating Soon (in progress)

Q2. Let L be a regular language. Then what can we say about the language L′={anan−1…a1∣n≥0,a1a2 an∈L}?

L′ is regular

L′ is not regular

L′ may or may not be regular

L′ cannot be generated by a regular expression

Answer: Updating Soon (in progress)

These are Theory of Computation Week 2 Nptel Assignment Answers

Q3. Any regular expression of size n can be converted to an NFA (with ϵ
-transitions) having at most (select the smallest possible asymptotic upper bound)

O(n) states

O(n2) states

O(2n) states

O(1) states

Answer: Updating Soon (in progress)

Q4. Which of the following regular expressions generates the following language?
L={w∈{0,1}∗∣wbegins with 1 and ends with 0}

1(0+1)∗0

(10)∗

1∗0∗

1(01)∗0

Answer: Updating Soon (in progress)

These are Theory of Computation Week 2 Nptel Assignment Answers

Q5. Which of the following regular expressions is equivalent to the regular expression (1+ϵ)(01)∗(0+ϵ)?

(0+ϵ)(01)∗(1+ϵ)

(1+ϵ)(10)∗(0+ϵ)

(0+ϵ)(10)∗(1+ϵ)

(01)∗+(10)∗

Answer: Updating Soon (in progress)

Q6. Which of the following regular expressions generates the complement of the language generated the regular expression (00+11)∗ ?

(00+11)∗(0+1)+(00+11)∗(01+10)(0+1)∗

(00+11)(0+1)∗+0(00)∗+1(11)∗

(01+10)(0+1)∗+0+1

(00+11)(0+1)∗+(0+1)(01+10)∗

Answer: Updating Soon (in progress)

These are Theory of Computation Nptel Assignment 2 Answers

Q7. Which of the following regular expressions generates the same language as the given DFA?

(a(b+ϵ)(ba)∗a+b(a+ϵ)(ab)∗b)∗

((b+ϵ)a(ab)∗a+(a+ϵ)b(ba)∗b)∗

((b+ϵ)a(ba)∗a+(a+ϵ)b(ab)∗b)∗

(a(a+ϵ)(ba)∗a+b(b+ϵ)(ab)∗b)∗

Answer: Updating Soon (in progress)

Q8. Let R and S be two regular expressions. Which of the following is equivalent to the regular expression S(S+RS)∗?

R(SR+R)∗

(RR∗S∗S∗)∗

(S+SR)∗R

RR∗S(RR∗S)∗

Answer: Updating Soon (in progress)