The regular languages are those languages that can be defined by regular expressions, or alternatively, by deterministic or non-deterministic finite automata.

• the real numbers are closed under ´ ,+,-, because
• such an operation on any two real number operands
• always results in another real number
• (the real number system is not closed under ¸ ) (why?)

• the operands are regular languages (remember, they are sets)
• and the operations are set operations: È , Ç , ¢ (set complement)
• we can ask the question: are regular languages closed under the three set operations?
• i.e. is the result also regular in each case?

Theorem 1. The regular languages are closed under È
Proof: Given RE₁ and RE₂ then (RE₁ + RE₂) is a RE that defines the union of the two languages, by definition of "+".

Theorem 2. The regular languages are closed under complementation
Proof: If a FA F accepts a language L, create a new FA F¢ from F by reversing its final and non-final states; that is, make each final state of F non-final in F¢, and make each non-final state of F final in F¢.

Preparation for Theorem 3:

DeMorgan’s Law: For any two sets A and B,

Proof (by Venn diagram):
 

A¢	B¢
A¢ Ç B¢

The last picture clearly also depicts (A È B)¢ .

Theorem 3. The regular languages are closed under Ç
Proof: Let A and B be regular languages. By DeMorgan’s laws,

Since A and B are regular, so are A¢ and B¢, by closure under complementation.  Hence A¢ È B¢ is regular, by closure under union. Hence (A¢ È B¢ )¢ is regular, again by closure under complementation. So A Ç B is regular.

This proof also offers a method of constructing a FA for A Ç B:  First construct FA for A¢ and B¢ by the method suggested in Theorem 2, then A¢È B¢ by the method given in Algorithm RE  Þ NFA for wiring together the FA's of A¢ and B¢ to create the FA of A¢È B¢ , and finally, the FA for (A¢È B¢ )¢, again by the method of Theorem 2.

This is also by construction of the FA that recognizes the intersection, but is more direct than the construction given with Proof 1.  Let’s illustrate the construction by an example:

Two languages:
L₁ = strings consisting of an of an odd number of a’s
L₂ = strings consisting of an of an even number of b’s

We want to define the intersection of these two languages: the language of strings that have an odd number of a’s and an even number of b’s.

Here are FA₁ and FA₂, the corresponding FA for these languages:

FA₁:
FA₂:

We will proceed in a way similar to that of finding L₁ È L₂:

This is a NFA. If we make it deterministic, then the new states will be sets of states each of which would be entered simultaneously for the same input, if run on the two machines separately.

So, any input which places this machine in a state containing both states 2 and 3 would be accepted by both original machines, and is in the intersection of the two languages.

Let’s make the above machine deterministic, using the tabular representation:
 

The bolded states are those in the final machine:

Notice that we can interpret the states; each tells us what kind of input string we have seen so far: