GATE CS 2024 Set 2 — Question 62

NAT+2 / -0MediumRegular ExpressionsFinite Automata & Regular LanguagesTheory of Computation

Theory of Computation → Finite Automata & Regular Languages → Regular Expressions

Last updated 20 August 2026

Question

Let

L_1

be the language represented by the regular expression

b^*ab^*(ab^*ab^*)^*

and

L_2 = \{ w \in (a + b)^* \mid |w| \leq 4 \}

, where

|w|

denotes the length of string

w

. The number of strings in

L_2

which are also in

L_1

is ___________

15 to 15

1.Analyze $L_1$ : The regular expression

b^*ab^*(ab^*ab^*)^*

represents the set of all strings over

\{a, b\}

that contain an odd number of 'a's.

2. Analyze $L_2$ :

L_2

is the set of all strings over

\{a, b\}

with length

|w| \leq 4

. This includes strings of length 0, 1, 2, 3, and 4.

3.Find $L_1 \cap L_2$ : We need to count the number of strings of length

\leq 4

that have an odd number of 'a's.

For any length $n \geq 1$ , the number of strings with an odd number of 'a's is exactly half of the total strings, i.e., $2^{n-1}$ .
Length 0: Total strings = $2^0 = 1$ (the empty string $\epsilon$ ). Number of 'a's = 0 (even). Count = 0.
Length 1: Count = $2^{1-1} = 2^0 = 1$ (string is 'a').
Length 2: Count = $2^{2-1} = 2^1 = 2$ (strings are 'ab', 'ba').
Length 3: Count = $2^{3-1} = 2^2 = 4$ (strings are 'aaa', 'abb', 'bab', 'bba').
Length 4: Count = $2^{4-1} = 2^3 = 8$ (strings are 'aaab', 'aaba', 'abaa', 'baaa', 'abbb', 'babb', 'bbab', 'bbba').

4. Total Count: Summing the counts for each length:

0 + 1 + 2 + 4 + 8 = 15