Question

Which of the following regular expressions denote a language comprising all possible strings of even length over the alphabet \(\{0,1\}\)?

• A. \((0+1)^*\)
• B. \((0+1)(0+1)^*\)
• C. \((00+01+10+11)^*\)
• D. \((0+1)(0+1)(0+1)^*\)

Hint:

To generate all even-length binary strings, think in pairs of symbols. The four possible pairs are \[ 00,\;01,\;10,\;11. \] Applying Kleene star to these pairs: \[ (00+01+10+11)^* \] produces every binary string whose length is \(0,2,4,6,\ldots\).

Answer 1

The Correct Option is C

Concept: A string is said to have even length if the number of symbols in the string is divisible by \(2\). Over the alphabet \[ \Sigma=\{0,1\}, \] all even-length strings can be viewed as concatenations of blocks containing exactly two symbols. Examples: \[ \epsilon,\;00,\;11,\;01,\;10,\;0011,\;1010,\;110011,\ldots \] A regular expression representing all such strings must generate symbols in pairs.

Step 1: Examine option (A).
\[ (0+1)^* \] This generates all possible strings over \(\{0,1\}\). Examples: \[ 0,\;1,\;00,\;101,\;1110,\ldots \] Both odd and even lengths are generated. Hence it is not correct.

Step 2: Examine option (B).
\[ (0+1)(0+1)^* \] This represents all non-empty strings. Lengths can be \[ 1,2,3,4,\ldots \] Thus odd-length strings are also included. Hence it is not correct.

Step 3: Examine option (C).
\[ (00+01+10+11)^* \] Each block \[ 00,\;01,\;10,\;11 \] contains exactly \(2\) symbols. The Kleene star allows any number of such blocks. Therefore possible lengths are \[ 0,2,4,6,8,\ldots \] which are all even numbers. Examples generated: \[ \epsilon, \] \[ 00, \] \[ 0110, \] \[ 111100, \] etc. Hence this regular expression generates all even-length binary strings.

Step 4: Examine option (D).
\[ (0+1)(0+1)(0+1)^* \] This generates strings of length at least \(2\). However, both odd and even lengths occur. For example, \[ 000 \] has length \(3\). Hence it is not correct.

Step 5: Write the final answer.
Only \[ (00+01+10+11)^* \] produces all possible strings of even length over \(\{0,1\}\). Therefore, \[ \boxed{(00+01+10+11)^*} \] Hence option (C) is correct.