The number of strings of length 4 that are generated by the regular expression…
2016
The number of strings of length 4 that are generated by the regular expression (0|∈)1+2* (3|∈), where | is an alternation character, {+, *} are quantification characters, and ∈ is the null string, is :
- A.
08
- B.
10
- C.
11
- D.
12
Attempted by 70 students.
Show answer & explanation
Correct answer: D
Answer: 12
Interpretation: The expression represents an optional leading '0', one or more '1's, zero or more '2's, and an optional trailing '3'.
Let a be 1 if '0' is present and 0 otherwise; let c be 1 if '3' is present and 0 otherwise. Let i be the number of '1's (i ≥ 1) and j be the number of '2's (j ≥ 0). We need a + i + j + c = 4.
No '0' and no '3' (a=0, c=0): i + j = 4 with i ≥ 1 ⇒ i = 1,2,3,4 → 4 strings.
Only leading '0' present (a=1, c=0): i + j = 3 with i ≥ 1 ⇒ i = 1,2,3 → 3 strings.
Only trailing '3' present (a=0, c=1): i + j = 3 with i ≥ 1 ⇒ i = 1,2,3 → 3 strings.
Both '0' and '3' present (a=1, c=1): i + j = 2 with i ≥ 1 ⇒ i = 1,2 → 2 strings.
Total strings of length 4 = 4 + 3 + 3 + 2 = 12.
A video solution is available for this question — log in and enroll to watch it.