Prove the intersection of regular languages is regular.

Question

A, B are regular languages.

1. Complement of a regular language is regular
2. Union is regular

Prove the intersection is regular.

Using these definitions the proof in my book is:

1. $\overline A$ is regular by 1

2. $\overline B$ is regular by 1

3. $\overline A \cup \overline B$ is regular by 2

4. $\overline{A\cup B}$ is regular by 1

5. $ A \cap B$ is regular by De Morgan's Law

Would someone mind explaining steps 4 & 5 or more specifically how you arrive at 4 from 3 and 5 from 4?

Thanks.

Answer 1

It's good that you don't understand how you can (possibly) get from 3. to 4. by appeal to principle 1. "the complement of a regular language is regular"; or from step 4., as written, to step 5. by De Morgan's Law. Step 3. to step 4. is just wrong, a typo or "think-o". In 4. "$\cup$" should be "$\cap$", as that follows from De Morgan's Law.

Here's a fix for the proof. For clarity, I'll refer to the two closure principles as P1. (complement) and P2. (union) rather than as 1. and 2. Steps 1. - 3. are unchanged:

1. $\overline A$ is regular -- by P1.
2. $\overline B$ is regular -- by P1.
3. $\overline A \cup \overline B$ is regular -- by P2.
4. $\overline {A \cap B}$ is regular -- by De Morgan's Law
5. ${A \cap B}$ is regular -- by P1.

The answer by @sasha shows another variation that gives a correct proof.

Answer 2

Basically by De Morgans law $A \cap B = \overline{(\overline A \cup \overline B)}$. Now we already know that regular languages are closed under complement thus $\overline A$ and $\overline B$ are regular ( given $A,B$ are regular languages ). We also know regular languages are closed under union thus $(\overline A \cup \overline B)$ is a regular language and again it's complement is also regular. Thus proved that regular languages are aslo closed under intersection.

Answer 3

Okay, misunderstanding there comes from a (wrong) premise that 4 should follow from 3 and 5 should follow from 4, and further conclusion that the book must be wrong. In fact it is not true that 2 follows from 1, and even 3 follows from 2. The fact that 3 follows from 1 and 2 is misleading and leads us to the wrong way of thinking.

In fact the book is fully correct, but it leaves the final touch for the reader. Statements 1-4 are mostly independent and should be treated as such. First 3 doesn't raise questions. Number 4 doesn't use 1-3 and is true simply because $A \cup B$ is regular (as complement to regular language). Number 5 is true because $A \cap B = \overline{\overline{A \cap B}} = \overline{\overline{A} \cup \overline{B}}$ (equation 1), and because we already know that $\overline{A} \cup \overline{B}$ is regular by 3, hence it once again boils down to a complement to regular language.

But wait, we didn't use 4 anywhere. It's all the same, but the book's way of thinking might be as follows. Let's substitute union of two regular languages $A \cup B$ in 4 with union of another two regular languages $\overline{A} \cup \overline{B}$ that is itself regular from 3. After substitution we read equation (1) above in reversed order to conclude $A \cap B$ is regular.