Let \(L_1\) be the language represented by the regular expression \(b^{*}ab^{*}(ab^{*}ab^{*})^{*}\) and \(L_2 = \{\, w \in (a + b)^{*} \mid |w| \le 4\}\), where \(|w|\) denotes the length of string \(w\). The number of strings in \(L_2\) which are also in \(L_1\) is ___________
Answer
15
Explanation
The part \(b^{*}ab^{*}\) contributes exactly one \(a\), each repetition of \((ab^{*}ab^{*})\) adds two more, and \(b\)’s may appear anywhere. So \(L_1\) is the set of strings with an odd number of \(a\)’s.
Count such strings of length at most 4:
- length 0: none;
- length 1: just \(a\), 1 string;
- length 2: one \(a\), \(\binom{2}{1} = 2\) strings;
- length 3: one or three \(a\)’s, \(3 + 1 = 4\) strings;
- length 4: one or three \(a\)’s, \(4 + 4 = 8\) strings.
Total: \(1 + 2 + 4 + 8 = 15\). For each length \(n \ge 1\), exactly half of the \(2^{n}\) strings qualify.
Answer: 15