Which one of the following regular expressions over {0,1} denotes the set of…

Concept: A regular expression avoids a forbidden substring like 100 only if its own construction rules out the exact adjacency that forms it — here, a 1 immediately followed by two consecutive 0s. The standard technique is to build every generated string only from fixed "blocks" that individually can never create that adjacency, however the blocks are chained together.

Application:

1. In 0*(10+1)*, the leading 0* produces any number of 0s before any 1 has occurred, so this part alone can never contain 100.

2. The remainder, (10+1)*, is built by repeatedly choosing one of two blocks, 10 or 1, and concatenating the chosen blocks in any order.

3. Concrete trace: choosing the blocks 1, 10, 1 gives 1 + 10 + 1 = 1101. Checking every length-3 window of 1101 — 110 and 101 — neither equals 100.

4. Conversely, take any string that avoids 100: strip its leading run of 0s, if any. The remainder starts with a 1 (or is empty), so every 0 left in it is preceded by a 1, and no such 0 can itself be followed by another 0 — that would already place 100 at that exact spot. So scanning the remainder left to right, every 1 is followed either by a single 0 (forming the block 10) or directly by the next 1 (forming the block 1) — or, if that 1 is the remainder’s very last symbol, it stands alone as a final block 1 — consuming the whole remainder into 1/10 blocks. This shows every 100-avoiding string is produced by 0*(10+1)*, matching the completeness half of the "denotes exactly this set" claim.

Cross-check: To ever produce 100, some 0 would have to be immediately followed by another 0 right after a 1. But the only zero-producing step inside (10+1)* is the single 0 tied to its own 10 block, and the symbol right after it is always either the 1 that starts the next block or the end of the string — never a second 0. So 100 can never occur, confirming this expression denotes exactly the required language: all strings over {0,1} that avoid 100 as a substring.