12
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ "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. $\endgroup$
    – Raphael
    Jun 29, 2012 at 12:48
  • $\begingroup$ I prefer changing title of this question. By itself question title is a wrong statement. $\endgroup$
    – nitishch
    Apr 20, 2014 at 8:27

2 Answers 2

Reset to default
19
$\begingroup$

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.

Improve this answer
$\endgroup$
8
  • $\begingroup$ I think I got it. But why is the complement of a regular language regular? I don't get that part. $\endgroup$
    – Kevin
    Jun 28, 2012 at 20:52
  • 1
    $\begingroup$ @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. $\endgroup$
    – Gilles 'SO- stop being evil'
    Jun 28, 2012 at 22:32
  • $\begingroup$ 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! $\endgroup$
    – Kevin
    Jun 29, 2012 at 6:48
  • $\begingroup$ 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. $\endgroup$
    – Mike B.
    Jun 29, 2012 at 7:55
  • 1
    $\begingroup$ @Kevin: Mike means that every regular language has a deterministic automaton to recognize it so you can always use one. $\endgroup$
    – reinierpost
    Jun 29, 2012 at 8:14
-4
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 5
    $\begingroup$ You have failed to satisfy the condition that $L_1 \cap L_2$ is regular. $\endgroup$
    – Andrej Bauer
    Jan 18, 2013 at 14:03

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