GATE CS 2024 Set 1 — Question 61

To find the number of strings of length $\le 5$ that are neither in $L(r)$ nor in $L(s)$, we first identify the strings in $L(r) \cup L(s)$ for each length $n \in \{0, 1, 2, 3, 4, 5\}$. Strings in $L(r)$ are of the form $0^n$ or $1^n$.

• $n=0$: $\epsilon$ (1 string)
• $n=1$: $0, 1$ (2 strings)
• $n=2$: $00, 11$ (2 strings)
• $n=3$: $000, 111$ (2 strings)
• $n=4$: $0000, 1111$ (2 strings)
• $n=5$: $00000, 11111$ (2 strings)

2. Regular Expression $s = 01^* + 10^*$:
Strings in $L(s)$ are of the form $01^n$ or $10^n$.

• $n=0$: None (0 strings)
• $n=1$: $0, 1$ (2 strings)
• $n=2$: $01, 10$ (2 strings)
• $n=3$: $011, 100$ (2 strings)
• $n=4$: $0111, 1000$ (2 strings)
• $n=5$: $01111, 10000$ (2 strings)

3. Union $L(r) \cup L(s)$:

• $n=0$: $\{\epsilon\}$ (1 string)
• $n=1$: $\{0, 1\}$ (2 strings)
• $n=2$: $\{00, 11, 01, 10\}$ (4 strings)
• $n=3$: $\{000, 111, 011, 100\}$ (4 strings)
• $n=4$: $\{0000, 1111, 0111, 1000\}$ (4 strings)
• $n=5$: $\{00000, 11111, 01111, 10000\}$ (4 strings)

Total strings in $L(r) \cup L(s)$ of length $\le 5 = 1 + 2 + 4 + 4 + 4 + 4 = 19$. Total = $2^0 + 2^1 + 2^2 + 2^3 + 2^4 + 2^5 = 1 + 2 + 4 + 8 + 16 + 32 = 63$. Count = Total - $|L(r) \cup L(s)| = 63 - 19 = 44$.