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.