edited by
646 views
3 votes
3 votes

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

edited by

2 Answers

Best answer
3 votes
3 votes
String 010 is not present in ‘q’ but present in ‘p’ whose length is 3.
selected by
0 votes
0 votes
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.$
Answer:

Related questions

0 votes
0 votes
1 answer
1
Bikram asked Aug 12, 2017
259 views
What is the regular expression corresponding to the above DFA?$(01 + (00)^*1)^*$$0^*10^*$$(10 + 0(00)^* (1 + 01) )^*$$0(00)^*10^*$
1 votes
1 votes
1 answer
3
1 votes
1 votes
1 answer
4
Bikram asked Aug 12, 2017
289 views
Choose the regular expression corresponding to the given DFA :$(00 ^*1 + 11^* 0) (0 + 1) ^*$$((11) ^* 0 + 00 ^* 1)(0 + 1) ^*$$(11) ^* (0 ^* 1 + 1^* 0) (0 + 1) ^*$$(11) ^*...