GATE CS 1997 Q6.4 — Regular Expressions and Finite Automata

To find the regular expression for the set of all strings over $\{0,1\}$ that do not contain $100$ as a substring:

1. Analyze the structure: Any such string can start with any number of $0$s, which is represented by $0^*$.
2. After the first $1$: Once the first $1$ appears, we cannot have two consecutive $0$s (i.e., $00$ is forbidden after a $1$). This means every $0$ that appears after the first $1$ must be immediately preceded by a $1$, forming the block $10$.
3. Formulate the suffix: Therefore, the remaining part of the string after the first $1$ can only be composed of blocks of $1$ and $10$. This is represented by the regular expression $(10+1)^*$.

Combining these two parts, we get the complete regular expression: $0^*(10+1)^*$.

Why other options are incorrect:

• Option A: $0^*(1+0)^*$ is equivalent to $(0+1)^*$, which generates all strings, including $100$.
• Option B: $0^*1010^*$ is extremely restrictive and cannot generate simple valid strings like $11$.
• Option C: $0^*1^*01^*$ cannot generate valid strings like $110110$, which do not contain $100$.