Prove that, if languages $R$ and $S$ are boring, then so are $R\cup S$ and $R\cdot S$

Question

This problem is adapted from "Mathematics for Computer Science" (Lehman, Leighton, Meyers, 2018).

Can anyone verify my solution attempt?

Problem

A word is a finite sequence of $0$'s and $1$'s, and a language is a set of words.

Let's say a language $S$ is $0$-finite when it includes only a finite number of words whose bits are all $0$'s, that is, when $S\cap 0^*$ is a finite set of words. A language $S$ is boring when either $S$ or $\overline{S}$ is $0$-finite.

(a) Explain why $\left\{00\right\}^*$ is not boring.

(b) Verify that, if $R$ and $S$ are boring, then so is $R\cup S$.

(c) Verify that, if $R$ and $S$ are boring, then so is $R\cdot S$ (Note: $R\cdot S$ is the language consisting of all the words that can be obtained by concatenating a word from $R$ with a word from $S$).

Hint: By cases: Whether $R$ and $S$ are both $0$-finite, whether $R$ or $R$ contains no all-$0$ words at all (including the empty word $\lambda$), and whether neither of these cases hold.

Solution attempt

(a) Let $S=\left\{00\right\}^*$. To show $S$ is not boring, I will show that both $S$ and $\overline{S}$ are not $0$-finite.

1. $S$ is not $0$-finite. Proof. By contradiction. If $S$ is $0$-finite, then there is a longest member in $S$ whose bits are all $0$s. Call this member $s$. However, $s' = s00$ is longer than $s$ and $s' \in S$, which is a contradiction.

2. $\overline{S}$ is not $0$-finite. Proof. By counter-example. $\overline{S}=\overline{\left\{00\right\}^*}$ is the language of all words that aren't formed by an even number of $0$'s. For example, the set $R$ of all words formed by an odd number of $0$'s (that is, $R = \left\{ w\text{ | }w = 0^{2n+1}\right\}$ where $n \geq 0$) is a subset of $\overline{S}$. Since $R$ has infinitely many members, this means that $\overline{S}$ contains an infinite number of all-$0$ words, and therefore $\overline{S}$ is not $0$-finite.

(b) Proof by cases:

1. $R$ and $S$ are both $0$-finite: The number of all-$0$ words in $R\cup S$ is: (number of all-$0$ words in $R$) + (number of all-$0$ words in $S$) - the number of all-$0$ words in $R\cap S$. So, $R\cup S$ is $0$-finite, and therefore boring.

2. $R$ is $0$-finite and $\overline{S}$ is $0$-finite: $\overline{R\cup S} = \overline{R}\cap \overline{S}$ is $0$-finite, because $\overline{S}$ is $0$-finite. So, $R\cup S$ is boring.

3. $\overline{R}$ is $0$-finite and $\overline{S}$ is $0$-finite: $\overline{R}\cap \overline{S}$ is $0$-finite, because $\overline{R}$ is $0$-finite and $\overline{S}$ is $0$-finite. So, $R\cup S$ is boring.

(c) I got stuck in this case. Here is a partial attempt:

1. $R$ and $S$ are both $0$-finite: The all-$0$ words in $R\cdot S$ are formed by the concatenation of all-$0$ from $R$ with all-$0$ from $S$. Since the number of all-$0$ words from R and S are finite, the number of all-$0$ words in $R\cdot S$ must also be finite. So, $R\cdot S$ is $0$-finite, and therefore boring.

2. Either $R$ or $S$ contains no all-$0$ words (including the empty word $\lambda$): $R\cdot S$ consists of words $r\cdot s$ where $r\in R$ and $s\in S$. Without loss of generality, assume $R$ contains no all-$0$ words. Since $r$ is not an all-$0$ word, then $r\cdot s$ can't be an all-$0$ word. So, $R\cdot S$ contains a finite number (zero) of all-$0$ words, and is therefore boring.

3. Neither of the cases above: I got stuck here. Any hints?

Answer 1

Suppose that $\overline{R}$ is $0$-finite. Then there exists $r \geqslant 0$ such that $0^r0^* \subseteq R \cap 0^*$. If $S \cap 0^*$ is empty, then $RS \cap 0^*$ is empty and thus $RS$ is $0$-finite. Otherwise, if $S \cap 0^*$ contains some word $0^s$. Then $$ 0^{r+s}0^* \subseteq (R \cap 0^*)(S \cap 0^*) \subseteq RS \cap 0^* $$ and hence $\overline{RS}$ is $0$-finite.

Answer 2

If $\overline R$ and $S$ are $0$-finite, then $R$ contains and infinite number of $0$-words, and so does $R\cdot S$, which means $\overline{R\cdot S}$ must contain a finite number of them. So, $R\cdot S$ is boring.

Similary, if both $\overline R$ and $\overline S$ are $0$-finite, $R$ and $S$ contain infinite $0$-words and so does $R\cdot S$, meaning $\overline {R\cdot S}$ is $0$-finite and again, $R\cdot S$ is boring. This takes care of all the cases.