2
$\begingroup$

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?

$\endgroup$
  • 4
    $\begingroup$ You should probably try harder proving or refuting your claims. $\endgroup$ – Yuval Filmus Feb 21 at 19:04
  • $\begingroup$ 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. $\endgroup$ – P. Soutzikevich Feb 22 at 13:40
6
$\begingroup$

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^*$.
$\endgroup$
4
$\begingroup$

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\}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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