Which of the following regular expressions describes the language — the set of…
2008
Which of the following regular expressions describes the language — the set of all strings over {0, 1} containing at least two 1's?
Answer: D. (0+1)*1(0+1)*1(0+1)* — The language is every binary string that contains at least two 1's, with the 1's allowed anywhere and any number of 0's in between, before, or after. To…
- A.
(0+1)* 11 (0+1)*
- B.
0*110*
- C.
0*10*10*
- D.
(0+1)*1(0+1)*1(0+1)*
Attempted by 86 students.
Show answer & explanation
Correct answer: D
The language is every binary string that contains at least two 1's, with the 1's allowed anywhere and any number of 0's in between, before, or after.
To guarantee two 1's that may sit anywhere, write a 1, then a 1, and surround and separate them by (0+1)* (which can match any string, including the empty string and additional 1's): (0+1)*1(0+1)*1(0+1)*. This matches '11' (1's adjacent), '101' (1's separated by a 0) and '111' (more than two 1's), i.e. exactly the strings with two or more 1's.
Why the others fail: (0+1)*11(0+1)* needs the two 1's to be consecutive, so it misses '101'. 0*110* only allows 0's around a single '11' block, missing '101' and '1001'. 0*10*10* fixes the count at exactly two 1's, so it misses '111' and other strings with three or more 1's.
Explore the full course: Ssc Je Imd Scientific Assistant Computer Science