Home › GATE CSE › computerscience › Theory 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)._
Related questions
Which class of grammars generates ALL recursively enumerable languages?What is a LEFTMOST DERIVATION?Which of the following languages is CONTEXT-FREE?Consider the grammar $S \to (S) \mid SS \mid \varepsilon$. The language generated isEvery regular language is also context-free. The PROOF construction isThe CYK algorithm parses a CFG in CNF. Its time complexity for a string of length $n$ isA LEFT-RECURSIVE rule in a CFG has the form $A \to A\alpha$ for some non-empty $\alpha$. WContext-free languages are CLOSED under which of the following operations?