prove/disprove regularity of languages

Question

Let $L_1 \in REG$ and $L_2 \notin REG$ prove or disprove:

$\forall L_1 ,L_2 \text{ } $ $\text{ }L_1^C \cup L_2\in REG \lor L_2\setminus L_1\in REG$

I think that it may be disproved, but I found it very hard to disprove, because:

if $L_2 \subseteq L_1$ then $L_2\setminus L_1 = \emptyset$

and if $L_1 \subseteq L_2$ then $ L_1^C \cup L_2 = (L_1 \cap L_2^C)^C = (L_1 \setminus L2)^C = \Sigma ^* $

and if $L_1 \cap L_2 = \emptyset$ then $ L_1^C \cup L_2 = L_1^C$

and in any other scenario, any counter-example that I tried to construct was too complicated to disprove the regularity of both languages.

I know that at least one of the languages must be not regular, and I proved it.

Answer 1

Let $\Sigma=\{0,1\}$ and denote by $|w|_1$ the number of occurrences of $1$ in $w \in \Sigma^*$. Pick $L_1 = \{w \in \Sigma^* \mid |w|_1 \equiv 1 \pmod 2\}$ and $L_2 = \{0^n1^n \mid n \ge 0\}$.

Suppose that $L' = L_1^C \cup L_2$ was regular. Then a necessary condition for $L'$ to be regular is for $L^{(1)} = L' \setminus L_1^C = L_2 \setminus L_1^C = \{ 0^{2k+1}1^{2k+1} \mid k \ge 0 \}$ to be regular.

Moreover, let $L^{(0)} = L_2 \setminus L_1 = \{ 0^{2k}1^{2k} \mid k \ge 0 \}$.

Both $L^{(1)}$ and $L^{(0)}$ are not regular. Suppose towards a contradiction that at least one of them, say $L^{(i)}$, was regular and let $p$ be any even integer that is not smaller than the the pumping length of $L^{(i)}$. Consider the word $0^{p+i}1^{p+i} \in L^{(i)}$. By the pumping lemma we know that there is some choice of $1 \le k \le p$ such that $0^{p+i-k} 0^{kh} 1^{p+i} \in L^{(i)}$ for every integer $h \ge 0$. Picking $h=0$ yields $0^{p+i-k} 1^{p+i} \in L^{(i)}$ but this is a contradiction.

Answer 2

First note that the statement is somewhat artificially made complex, probably to muddle the solution.

The languages considered are $L_1^C \cup L_2$ and $L_2 \setminus L_1 = L_2 \cap L_1^C$. Now replace $L_1$ by its complement, and we obtain $L_1 \cup L_2$ and $L_1 \cap L_2$.

In order to find a counter example it suffices to find a regular $L_1$ and a nonregular $L_2$ such that both their union and intersection are nonregular.

Assume the alphabet is $\Sigma= \{0,1\}$. Choose any non-regular language $L\subseteq \Sigma^*$. Then let $L_2 = \Sigma \cdot L$, which means that both $0{\cdot}\Sigma^* \cap L_2$ and $1{\cdot}\Sigma^* \cap L_2$ are irregular, as they are basically two disjoint copies of $L$ within $L_2$.

Now consider $L_1 = 0{\cdot} \Sigma^*$.