Test by Bikram | Theory of Computation | Test 2 | Question: 5

Question

Given two regular expressions:

• $p = (0^* 1^* )^*$  and  
• $q = 0^* + 1^* + 0^*1 + 10^*$

The length of the smallest string that is present in the language corresponding to regular expression ‘$p$’ and not present in the language corresponding to regular expression ‘$q$’ is ________.

Comments

why is epsilon (length 0)  not the answer?

---

how come epsilon(length=0) not the answer??

Answer 1

String 010 is not present in ‘q’ but present in ‘p’ whose length is 3.

Comments

Yes. It is

---

Am not getting this please make clear ..

---

Sir, 011 is also correct na?

Answer 2

Lets consider the binary strings in lexicographic order for lengths starting from $0$ on wards, which will be $\{\epsilon, 0, 1, 01, 10, 11, 000, 001, 010, \ldots \}.$

Here, $p = \Sigma^*$ and generates every binary string.

$\epsilon, 0, 1, 01, 10,11, 000, 001$ are generated by $q$ also but $010$ is not generated by $q.$ $\mid 010 \mid = 3.$

Correct answer: $3.$