Which one of the following regular expressions over {0,1} denotes the set of…
1997
Which one of the following regular expressions over {0,1} denotes the set of all strings not containing 100 as a substring?
- A.
0* (1+0)*
- B.
0*1010*
- C.
0*1*01*
- D.
0*(10+1)*
Attempted by 16 students.
Show answer & explanation
Correct answer: D
The substring 100 occurs when a 1 is followed by two consecutive 0s.
In 0*(10+1)*:
0* allows leading zeros.
(10+1)* generates strings using only the blocks 1 and 10.
Therefore, a 1 can never be followed by two zeros, so 100 cannot occur.