# prove/disprove regularity of languages

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.

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.

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^*$$.