0
$\begingroup$

1) Given $L_1$ is a regular language and $L_2$ is a non-regular language, the intersection of $L_1$ and $L_2$ is a finite language, how to prove that the union of $L_1$ and $L_2$ is a non-regular language?

2) Given $L_1$ is a regular language and $L_2$ is a non-regular language, the intersection of $L_1$ and $L_2$ is an infinite language, how to prove that the union of $L_1$ and $L_2$ is a regular language.

I have tried my best to prove this, I tried pumping lemma and Demorgan's law and haven't worked it out. Asking for help with sincerity.

$\endgroup$
1
$\begingroup$

1) is equivalent to the following claim

Let $L_1$ be a regular language, $L_2$ any language. Assume that $L_1 \cup L_2$ is regular and that $L_1 \cap L_2$ is finite. Then $L_2$ is regular.

This is easy to prove.

2) is false.

Take $L_1$ an infinite regular language, $L_2$ the union of $L_1$ and a non-regular language over a totally different alphabet. Then $L_1 \cap L_2 = L_1$ is infinite and $L_1 \cup L_2 = L_2$ is non-regular.

$\endgroup$
  • $\begingroup$ I don't understand why the first question is equivalent to your claim.What I want to prove is that L1∪L2 is a non-regular language, why do you assume L1∪L2 is regular? Is this converse negative proposition or something ? And why is the second statement wrong?I can't think up a counterexample. Thank you for your reply any way. $\endgroup$ – sigmatic z Mar 10 '18 at 14:22
  • $\begingroup$ For the first question: this is just the equivalence between $P \to Q$ and $\lnot Q \to \lnot P$. For the second question: I've essentially given a counterexample. $\endgroup$ – Magdiragdag Mar 10 '18 at 14:24
  • $\begingroup$ I got it now,you are right. I found I was so stupid...really appreciate your patience:) $\endgroup$ – sigmatic z Mar 10 '18 at 14:53
0
$\begingroup$

(1) Observe that $$L_2 = \bigl((L_1 \cup L_2) \setminus L_1\bigr) \cup (L_1 \cap L_2))$$ Therefore, if $L_1$, $L_1 \cup L_2$ and $L_1 \cap L_2$ are regular, so is $L_2$. In your case, $L_1 \cap L_2$ is finite and hence regular. Thus if $L_1 \cup L_2$ were regular, then $L_2$ would also be regular.

(2) is false, even on a one-letter alphabet. Take $L_1 = (a^2)^*$ and $L_2 = (a^2)^* \cup \{a^p \mid \text{$p$ prime}\}$. Then $L_1 \cap L_2 = L_1$ is infinite (and regular!), but $L_1 \cup L_2 = L_2$ is nonregular.

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