Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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 \backslash (L_2 \cap L_1)$. This one is regular. I can construct a finite automata 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 is 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 \backslash (L_1 \cap L_2)$ (regular) and $L_2$ (not regular) is not regular?

share|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. –  hatter Apr 20 at 8:27
add comment

2 Answers

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|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
1  
@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
1  
@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
show 1 more comment

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|improve this answer
2  
You have failed to satisfy the condition that $L_1 \cap L_2$ is regular. –  Andrej Bauer Jan 18 '13 at 14:03
add comment

protected by Community Apr 19 at 13:12

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

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.