GATE CS 2024 Set 2 Q52 — Regular Expressions and Finite Automata

First, let us analyze the language $L_1$ represented by the regular expression $b^* a b^* (a b^* a b^*)^*$.

• The term $b^* a b^*$ generates strings containing exactly one $a$.
• The term $(a b^* a b^*)^*$ generates strings containing an even number of $a$'s (multiples of 2).

Combining these, the regular expression generates strings with an odd number of $a$'s. Thus, $L_1$ is the set of all strings over $\{a, b\}$ containing an odd number of $a$'s.

The language $L_2$ consists of all strings over $\{a, b\}$ of length at most $4$. We need to find the number of strings in $L_2 \cap L_1$, which are strings of length $n \le 4$ with an odd number of $a$'s.

For any length $n \ge 1$, exactly half of the $2^n$ possible strings contain an odd number of $a$'s, which is $2^{n-1}$ strings. We calculate this for each length $n$:

• Length $n = 0$: $0$ strings (even number of $a$'s).
• Length $n = 1$: $2^0 = 1$ string ($\{a\}$).
• Length $n = 2$: $2^1 = 2$ strings ($\{ab, ba\}$).
• Length $n = 3$: $2^2 = 4$ strings ($\{abb, bab, bba, aaa\}$).
• Length $n = 4$: $2^3 = 8$ strings.

Summing these up, the total number of strings is: