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.


2 Answers 2


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.