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 ________

Let $\Sigma = \{0, 1\}$.

1. Total number of strings of length $\le 5$: The total number of binary strings of length $k$ is $2^k$.

   $$\sum_{k=0}^{5} 2^k = 1 + 2 + 4 + 8 + 16 + 32 = 63$$

2. **Strings in $L(r) = L(0^* + 1^*)$ of length $\le 5$:**

   • Length 0: $\epsilon$ (1 string)

   • Length 1: $0, 1$ (2 strings)

   • Length 2: $00, 11$ (2 strings)

   • Length 3: $000, 111$ (2 strings)

   • Length 4: $0000, 1111$ (2 strings)

   • Length 5: $00000, 11111$ (2 strings)

   Total in $L(r)$ of length $\le 5$ is $1 + 2 \times 5 = 11$ strings.

3. **Strings in $L(s) = L(01^* + 10^*)$ of length $\le 5$:**

   • Length 1: $0, 1$ (already in $L(r)$)

   • Length 2: $01, 10$ (2 new strings)

   • Length 3: $011, 100$ (2 new strings)

   • Length 4: $0111, 1000$ (2 new strings)

   • Length 5: $01111, 10000$ (2 new strings)

   Number of distinct strings in $L(s) \setminus L(r)$ of length $\le 5$ is $2 \times 4 = 8$ strings.

4. Total strings in $L(r) \cup L(s)$ of length $\le 5$:

   $$|L(r)| + |L(s) \setminus L(r)| = 11 + 8 = 19$$

5. Strings of length $\le 5$ neither in $r$ nor in $s$:

   $$63 - 19 = 44$$