The GATE Grind

GATE 2024 CS (CS2) – Question 62

Theory of Computation · Regular Expressions and Finite Automata · 2 marks · Numerical answer

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 ___________

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: 15

Explanation

L1 is the set of strings with an odd number of a's. Counting odd-a strings by length: length 1: 1; length 2: 2; length 3: 4; length 4: 8. Total = 15.