## NPTEL Theory of Computation Week 2 Assignment Answers 2024

1. Which of the following is equivalent to the set described by the regular expression 11^{∗}00^{∗}?

- {1
^{m}0^{m}|m>0 is a natural number} - {1
^{m}0^{n}|m,n>0 are natural numbers} - {1
^{m}0^{m}|m≥0 is a natural number} - {1
^{m}0^{n}|m,n≥0 are natural numbers}

Answer :-For ANswer Click Here

2. Let L be a regular language. Then what can we say about the language

L′={a_{n}a_{n}−1…a1∣n≥0,a_{1}a_{2}…a_{n}∈L}?

- L′ is regular
- L′ is not regular
- L′ may or may not be regular
- L′ cannot be generated by a regular expression

Answer :-For ANswer Click Here

3. 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 :-

4. 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 :-

5. 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 :-For ANswer Click Here

6. 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 :-

7. 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 :-

8. 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 :-For ANswer Click Here