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 _________
Answer
44
Explanation
There are \(1 + 2 + 4 + 8 + 16 + 32 = 63\) binary strings of length 0 to 5, counting the empty string.
- \(r = 0^{*} + 1^{*}\): the empty string, plus the all-0 and the all-1 string of each length 1 to 5: \(1 + 5 \times 2 = 11\) strings.
- \(s = 01^{*} + 10^{*}\): one string \(01\cdots1\) and one string \(10\cdots0\) of each length 1 to 5: 10 strings.
- The strings 0 and 1 belong to both languages.
So \(11 + 10 - 2 = 19\) strings are in \(r\) or \(s\), and \(63 - 19 = 44\) are in neither. Forgetting to remove the two shared strings gives 42.
Answer: 44