Official PYQ · 2024Set 1 · Q51Regular Expressions and Finite AutomataNAT2 marks

GATE CS 2024 Set 1 Q51 — Regular Expressions and Finite Automata

Consider the following two regular expressions over the alphabet

\{0,1\}

r= 0^{*}+1^{*}

s = 01^{*} + 10^{*}

The total number of strings of length less than or equal to

5

, which are neither in

r

nor in

s

, is ________.

View worked solution

Answer: 44

We need to find the number of binary strings $w$ of length $|w| \le 5$ that are neither in $L(r)$ nor in $L(s)$ , where:

$r = 0^* + 1^*$ (strings consisting of only $0$ s or only $1$ s)
$s = 01^* + 10^*$ (strings starting with $0$ followed by any number of $1$ s, or starting with $1$ followed by any number of $0$ s)

Let $2^n$ be the total number of binary strings of length $n$ . We analyze the number of strings of length $n$ in $L(r) \cup L(s)$ for each $n \in \{0, 1, 2, 3, 4, 5\}$ :

Length ( $n$ )	Total ( $2^n$ )	$L(r)$ Strings	$L(s)$ Strings	Union $\|L(r) \cup L(s)\|$	Neither ( $2^n - \|L(r) \cup L(s)\|$ )
0	1	$\{\epsilon\}$ (1)	$\emptyset$ (0)	1	$1 - 1 = 0$
1	2	$\{0, 1\}$ (2)	$\{0, 1\}$ (2)	2	$2 - 2 = 0$
2	4	$\{00, 11\}$ (2)	$\{01, 10\}$ (2)	4	$4 - 4 = 0$
3	8	$\{000, 111\}$ (2)	$\{011, 100\}$ (2)	4	$8 - 4 = 4$
4	16	$\{0000, 1111\}$ (2)	$\{0111, 1000\}$ (2)	4	$16 - 4 = 12$
5	32	$\{00000, 11111\}$ (2)	$\{01111, 10000\}$ (2)	4	$32 - 4 = 28$

Summing the counts of "Neither" for all lengths $0 \le n \le 5$ :

\text{Total} = 0 + 0 + 0 + 4 + 12 + 28 = 44

Free practice · Your answers on this page are not saved.

Published 10 Oct 2026

Report a correction

Browse this topic

More Regular Expressions and Finite Automata questions

GATE CS 2024 Set 1 Q51 — Regular Expressions and Finite Automata

Related questions