GATE CSE 2024 | Set 2 | Question: 52

Question

Let $L_{1}$ be the language represented by the regular expression $b^{*} a b^{*}\left(a b^{*} a b^{*}\right)^{*}$ and $L_{2}=\left\{w \in(a+b)^{*}|| w \mid \leq 4\right\}$, where $|w|$ denotes the length of string $w$. The number of strings in $L_{2}$ which are also in $L_{1}$ is _________.

Answer 1

in total 15 strings of L2 are present in L1

Answer 2

15

Answer 3

If we try to analyze the regular language, we get L1 = set of strings where number of a's is odd.

For all strings of length 'x' half of them will have odd number of a's i.e. x/2 (think why)

So, we can sum up half of total strings of all lengths (upto 4) in L1 = 1/2 + 2/2 + 4/2 + 8/2 + 16/2 = 15.

These all will be readily available in L2 since it is (a+b)*