Which of the following regular expressions, each describing a language of…
2017
Which of the following regular expressions, each describing a language of binary numbers (MSB to LSB) that represents non-negative decimal values, does not include even values ?
(1) \(0^*1^+0^*1^*\) (2) \(0^*1^*0^+1^*\) (3) \(0^*1^*0^*1^+\) (4) \(0^+1^*0^*1^*\)
Where \(\{+, ∗\}\) are quantification characters.
- A.
1
- B.
2
- C.
3
- D.
4
Attempted by 94 students.
Show answer & explanation
Correct answer: C
Short answer: The regular expression 0^*1^*0^*1^+ generates only binary strings that end with 1, so it cannot represent even numbers (which end with 0).
Reasoning (check each regular expression):
0^*1^+0^*1^*: Can end with 0 because the 1^* at the end may be empty while the preceding 0^* can provide trailing zeros. Example: "10" matches (0^*=empty, 1^+="1", 0^*="0", 1^*=empty). So this language includes even numbers.
0^*1^*0^+1^*: Can end with 0 because the final 1^* can be empty and 0^+ supplies at least one zero. Example: "0" matches (0^*=empty, 1^*=empty, 0^+="0", 1^*=empty). So this language includes even numbers.
0^*1^*0^*1^+: Always ends with at least one 1 because of the final 1^+. Therefore every matched string ends with 1 and represents an odd number. Examples: "1", "01", "101" all match; no string from this pattern can end with 0. Hence this language does not include even values.
0^+1^*0^*1^*: Can end with 0 because the trailing 1^* may be empty and 0^* can provide zeros. Example: "0" matches (0^+="0", others empty). So this language includes even numbers.
Conclusion: 0^*1^*0^*1^+ is the only given regular expression that cannot produce even values because it forces the final bit to be 1.