Practice free →
HomeGATE CSEcomputerscienceTheory of Computation › Which of the following is a CORRECT regular expr…

Which of the following is a CORRECT regular expression for the language $L = \{w \in \{0,1\}^* \mid w \text{ contains at least one } 0\}$?

A$0^* 1^*$, only 0s then 1s
B$(0+1)^* 0 (0+1)^*$
C$0 (0+1)^*$, starts with 0
D$(0+1)^*$, matches every string
Answer & Solution
Correct answer: B. $(0+1)^* 0 (0+1)^*$
1. We need to ENSURE at least one 0 appears somewhere in the string. 2. The cleanest way: insert a literal $0$ in the regex, sandwiched between any-strings: $(0+1)^* 0 (0+1)^*$. 3. Decoding: $(0+1)^*$ matches anything before the guaranteed 0; then the literal 0; then $(0+1)^*$ matches anything after. 4. Option A would force all 0's first then all 1's (too restrictive). Option C requires the string to START with 0. Option D matches ALL strings including those with zero 0's. 5. Equivalent alternative: $\overline{1^*}$ (complement of all-1's strings) — same language. _Source: Jeff Erickson, "Models of Computation", §2.3 (Regular expressions, building languages)._
Solve this in the app — GATE CSE practice & 24k+ MCQs →
Related questions