Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $L_1$ be regular, $L_1 \cap L_2$ regular, $L_2$ not regular. Show that $L_1 \cup L_2$ is not regular or give a counterexample.

I tried this: Look at $L_1 \setminus (L_2 \cap L_1)$. This one is regular. I can construct a finite automaton for this: $L_1$ is regular, $L_2 \cap L_1$ is regular, so remove all the paths (finite amount) for $L_1 \cap L_2$ from the finite amount of paths for $L_1$. So there are a finite amount of paths left for this whole thing. This thing is disjoint from $L_2$, but how can I prove that the union of $L_1 \setminus (L_1 \cap L_2)$ (regular) and $L_2$ (not regular) is not regular?

share|cite|improve this question
"so remove all the paths (finite amount) for $L_1\cap L_2$ from the finite amount of paths for $L_1$" -- what is that supposed to mean? The usual way to construct an automaton for the difference is by using $A \setminus B = A \cap \overline{B}$ and the well-known constructions for complement and intersection. – Raphael Jun 29 '12 at 12:48
I prefer changing title of this question. By itself question title is a wrong statement. – nitishch Apr 20 '14 at 8:27

We can prove this by contradiction. Lets define $\overline{L_1} = \Sigma^* \setminus L_1$. Then we can reformulate $L_2$:

$L_2 = ((L_1 \cup L_2) \setminus L_1) \cup (L_1 \cap L_2) = ((L_1 \cup L_2) \cap \overline{L_1}) \cup (L_1 \cap L_2)$

We know:

  • Regular Languages are closed under union, intersection and complement
  • $\overline{L_1}$ and $L_1 \cap L_2$ are regular
  • $L_2$ is not regular

Now assume $L_1 \cup L_2$ is regular: Then $((L_1 \cup L_2) \cap \overline{L_1}) \cup (L_1 \cap L_2)$ is regular (as it is only a union/intersection of regular languages), so $L_2$ would be regular. That is a contradiction, therefore our assumption is false, and $L_1 \cup L_2$ can not be regular.

share|cite|improve this answer
I think I got it. But why is the complement of a regular language regular? I don't get that part. – Kevin Jun 28 '12 at 20:52
@Kevin This is a well-known lemma, so you should find a proof in any textbook. One proof method is to take a finite automaton and swap the accepting and non-accepting states: you get an automaton that recognizes the complement language. – Gilles Jun 28 '12 at 22:32
And what for non-deterministic finite automata? Suppose we have an automata. $A = \{a,b\}$, one initial state, two arrows from that state with $a$ to another state. One of those states is accepting and one not. So $L(M)=\{a\}$. If we now swap the accepting states, it will still accept $\{a\}$, so it does not hold that it that accepts the complement language! – Kevin Jun 29 '12 at 6:48
Gilles' proof works only for deterministic finite automata, which - for regular languages - isn't a restriction. But as he said, this lemma can be found in any textbook. – Mike B. Jun 29 '12 at 7:55
@Kevin: Mike means that every regular language has a deterministic automaton to recognize it so you can always use one. – reinierpost Jun 29 '12 at 8:14

That is wrong. Consider $L_1 = \{a, b\}^*$, $L_2 = \{a^n b^n : n \ge 0\}$. $L_1$ is regular, $L_2$ isn't; but $L_1 \cup L_2 = L_1$.

share|cite|improve this answer
You have failed to satisfy the condition that $L_1 \cap L_2$ is regular. – Andrej Bauer Jan 18 '13 at 14:03

protected by Community Apr 19 '14 at 13:12

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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