# Union of a regular and a non-regular language

Let's say we have $$L_1$$ which is a regular language and $$L_2$$ which is not.

I understand that if $$L_1 \cup L_2 = \Sigma^*$$ then $$L_1 \cup L_2$$ is a regular language.

Does that implicitly mean that if $$L_1 \cup L_2 \neq \Sigma^*$$ then $$L_1 \cup L_2$$ is non-regular?

• You should probably try harder proving or refuting your claims. – Yuval Filmus Feb 21 at 19:04
• Both are quality answers and I appreciate the time of both. I'm changing the accepted answer to that of Peter Taylor's. While I understood the example that Yuval Filmus gave, I found Peter's explanation a bit more amateur-friendly. – P. Soutzikevich Feb 22 at 13:40

## 2 Answers

I assume you can already prove that the union, intersection, and complement of regular languages is regular.

Let $$L_1$$ be regular and $$L_2$$ be non-regular. Then you should also be able to prove:

1. At most one of $$L_1 \cup L_2$$ and $$L_1 \cap L_2$$ is regular.
2. If $$L_1 \subset L_2$$ then their union is irregular. (You should also be able to construct an example).
3. If $$L_2 \subset L_1$$ then their union is regular. (You should also be able to construct an example).
4. If the complement of $$L_1$$ contains at least two words, there is a regular language $$L_3$$ such that $$L_1 \cap L_3 = \emptyset$$ and $$L_1 \cup L_3 \subsetneq \Sigma^*$$. Then either $$L_3 \cup L_2$$ is regular or $$L_1$$, $$L_3 \cup L_2$$ are an example of a regular and an irregular language whose union is regular but where neither is a subset of the other and their union is not $$\Sigma^*$$.

If $$P$$ implies $$Q$$ then it doesn't mean that not $$P$$ implies not $$Q$$.

In your case, you can take $$L_1 = 0\Sigma^*$$ and $$L_2=\{0^{n+1}1^n : n \geq 0\}$$.