# Proving a language is not regular

If two languages L1 and L2 are regular than so is their intersection.

If follows that, for two languages L1 and L2, if L1 intersection L2 is not regular and L1 IS regular than L2 is not regular.

I am having a hard time proving this. Since I am dealing with regular languages, I decided to build DFA's for them to help my proof. However, this does not help with my proof if I am supposed to prove the irregularity of a language. How do you prove a language is not regular if you cannot construct a DFA/NFA for them? Is pumping lemma the only way?

-
Simple standard logic suffices. $P(A) \land P(B) \implies P(A \cap B)$ is equivalent (by contraposition) to $\neg P(A \cap B) \implies \neg (P(A) \land P(B))$. Then simplifying and pairing up with $P(A)$ should yield the desired result. – dtldarek Jan 28 '13 at 22:32

## 2 Answers

The second statement logically follows from the first without any knowledge of how languages or sets work:

$$Regular(L_1) \wedge Regular(L_2) \to Regular (L_1 \cap L_2)$$ $$\lnot Regular (L_1 \cap L_2) \wedge Regular(L_1) \to \lnot Regular(L_2)$$

To prove that the first statement is true, show how you could construct a DFA for the intersection of two languages for which you already have DFAs.

Edit: Here is a slightly more detailed outline. Let $A = Regular(L_1)$, $B = Regular(L_2)$, $C = Regular(L_1 \cap L_2)$. The first 3 lines are given, and you want to show the last line ($\lnot B$).

Given: $$(A \wedge B) \to C$$ $$\lnot C$$ $$A$$ From line 1: $$\lnot C \to \lnot (A \wedge B)$$ From lines 2 and 4: $$\lnot (A \wedge B)$$ From line 5: $$\lnot A \lor \lnot B$$ From lines 3 and 6: $$\lnot B$$

This isn't a formal proof--I haven't established a set of inference rules, and listed the rule used at each step. But it should give you a starting place. You'll have to look up which inference rules you're allowed to use in your course.

-
Thanks for the reply. I have no problem proving the intersection of two languages is regular, proving that if one of the two languages are regular and the intersection is not regular than the other language must be not regular is what I am having a tough time proving... – Epsilon Jan 28 '13 at 22:38
@MHZ, I don't really get what you want. Matthew provided a valid proof for what you asked. – sxd Jan 28 '13 at 22:39
I dont understand how Matthew's proof, proves that: if one of the two languages are regular and the intersection is not regular than the other language must be not regular. I appreciate any explanation... – Epsilon Jan 28 '13 at 22:45
"To prove that the first statement is true, etc...", what if I need to prove the second statement is true? – Epsilon Jan 28 '13 at 22:47
@MHZ, check my answer, that should clear things up. – sxd Jan 28 '13 at 22:50

Proving this can be done just in the following way:

We have: (1) if $L_1$ and $L_2$ are regular, then, $L_1 \cap L_2$ is regular as you probably know.

However, if $L_1 \cap L_2$ is not regular and $L_1$ is regular, then $L_2$ cannot be regular since by (1) if $L_2$ were regular, $L_1\cap L_2$ is regular, which contradicts our assumption.

-