# $L_1$ is a regular language, $L_2$ is a non-regular language, the intersection $L_1 \cap L_2$ is finite language

1) Given $L_1$ is a regular language and $L_2$ is a non-regular language, the intersection of $L_1$ and $L_2$ is a finite language, how to prove that the union of $L_1$ and $L_2$ is a non-regular language?

2) Given $L_1$ is a regular language and $L_2$ is a non-regular language, the intersection of $L_1$ and $L_2$ is an infinite language, how to prove that the union of $L_1$ and $L_2$ is a regular language.

I have tried my best to prove this, I tried pumping lemma and Demorgan's law and haven't worked it out. Asking for help with sincerity.

1) is equivalent to the following claim

Let $L_1$ be a regular language, $L_2$ any language. Assume that $L_1 \cup L_2$ is regular and that $L_1 \cap L_2$ is finite. Then $L_2$ is regular.

This is easy to prove.

2) is false.

Take $L_1$ an infinite regular language, $L_2$ the union of $L_1$ and a non-regular language over a totally different alphabet. Then $L_1 \cap L_2 = L_1$ is infinite and $L_1 \cup L_2 = L_2$ is non-regular.

• I don't understand why the first question is equivalent to your claim.What I want to prove is that L1∪L2 is a non-regular language, why do you assume L1∪L2 is regular? Is this converse negative proposition or something ? And why is the second statement wrong?I can't think up a counterexample. Thank you for your reply any way. – sigmatic z Mar 10 '18 at 14:22
• For the first question: this is just the equivalence between $P \to Q$ and $\lnot Q \to \lnot P$. For the second question: I've essentially given a counterexample. – Magdiragdag Mar 10 '18 at 14:24
• I got it now,you are right. I found I was so stupid...really appreciate your patience:) – sigmatic z Mar 10 '18 at 14:53

(1) Observe that $$L_2 = \bigl((L_1 \cup L_2) \setminus L_1\bigr) \cup (L_1 \cap L_2))$$ Therefore, if $L_1$, $L_1 \cup L_2$ and $L_1 \cap L_2$ are regular, so is $L_2$. In your case, $L_1 \cap L_2$ is finite and hence regular. Thus if $L_1 \cup L_2$ were regular, then $L_2$ would also be regular.

(2) is false, even on a one-letter alphabet. Take $L_1 = (a^2)^*$ and $L_2 = (a^2)^* \cup \{a^p \mid \text{$p$prime}\}$. Then $L_1 \cap L_2 = L_1$ is infinite (and regular!), but $L_1 \cup L_2 = L_2$ is nonregular.