Question 61

Total binary strings of length $\le 5$:

Count strings in $L(r) \cup L(s)$ of length $k \in \{0, 1, 2, 3, 4, 5\}$:

• $k = 0$: $\epsilon \in L(r)$ $\rightarrow$ 1 string
• $k = 1$: 0, 1 $\in L(r) \cup L(s)$ $\rightarrow$ 2 strings
• $k = 2$: 00, 11 $\in L(r)$ and 01, 10 $\in L(s)$ $\rightarrow$ 4 strings
• $k = 3$: 000, 111 $\in L(r)$ and 011, 100 $\in L(s)$ $\rightarrow$ 4 strings
• $k = 4$: 0000, 1111 $\in L(r)$ and 0111, 1000 $\in L(s)$ $\rightarrow$ 4 strings
• $k = 5$: 00000, 11111 $\in L(r)$ and 01111, 10000 $\in L(s)$ $\rightarrow$ 4 strings

Total strings in $L(r) \cup L(s)$ of length $\le 5$ is $1 + 2 + 4 + 4 + 4 + 4 = 19$.

Strings in neither $r$ nor $s$: