KTU University Exam 2021

Question

Let r1=(0+1)*, r2=0*1+10*+0*+1*. What is the length of the smallest string that is present in language corresponds to regular expression r1 and not present in language corresponds to regular expression r2.

1. 2

2. 3

100. 1

500. none of the above

Comments

Answer key has given the answer as a. 2

Answer 1

Given,

r1 = (0+1)* = set of all strings of 0 or 1 

r2 = 0*1+10*+0*+1*

    = { ɛ, 0, 1, 00, 01, 10, 11, 000, 001, 100, 111, ….}

Since, 010, 011, 101, 110 is present in r1 but not in r2 and length is 3

so ans is b. 

Comments

Thank you for the answer Yaman, even I answered b. 3, but the released answer key mentioned a. 2 as the answer; which is why I posted the question in GO.

---

Try generating 11 with R2.

 

---

In r2, there is 1* so it generates 11.

;)

---

Indeed i completely miss out on that. Thanks mate.

Answer 2

11 is the smallest expression formed by r2

00,01,10 are those present in r1 and not present in r2

length is 2

Comments

r2 = 0*1 + 10* + 0* + 1*

Can't 00,  01, 10 be derived from 0*, 0*1, 10* respectively?

---

I think it's mentioned smallest string in question

So I took r2 without * and got the smallest