Since the union of two regular sets is always a regular set, regular sets are closed under the union operation. Similarly, regular sets are closed under concatenation and closure operations, because the concatenation of a regular sets is also a regular set, and the closure of a regular set is also a regular set.

Regular sets are also closed under the complement operation, because if *L*(*M*) is a language accepted by a finite automata *M*, then the complement of *L*(*M*) is Σ*− *L*(*M*). If we make all final states of *M* nonfinal, and we make all nonfinal states of *M* final, then the automata accepts Σ*− *L*(*M*); hence, we conclude that the complement of *L*(*M*) is also a regular set. For example, consider the transition diagram in Figure 1.

The transition diagram of the complement to the automata shown in Figure 1 is shown in Figure 2.

Since the regular sets are closed under complement as well as union operations, they are closed under intersection operations also, because intersection can be expressed in terms of both union and complement operations, as shown below:

where *L*_{1} denotes the complement of *L*_{1}.

An automata for accepting *L*_{1} ∩ *L*_{2} is required in order to simulate the moves of an automata that accepts *L*_{1} as well as the moves of an automata that accepts *L*_{2} on the input string *x*. Hence, every state of the automata that accepts *L*_{1} ∩ *L*_{2} will be an ordered pair [*p*, *q*], where *p* is a state of the automata accepting *L*_{1} and *q* is a state of the automata accepting *L*_{2}.

Therefore, if *M*_{1} = (*Q*_{1}, Σ, δ_{1}, *q*_{1}, *F*_{1}) is an automata accepting *L*_{1}, and if *M*_{2} = (*Q*_{2}, Σ, δ_{2}, *q*_{2}, *F*_{2}) is an automata accepting *L*_{2}, then the automata accepting *L*_{1} ∩ *L*_{2} will be: *M* = (*Q*_{1} � *Q*_{2}, Σ, δ, [*q*_{1}, *q*_{2}], *F*_{1} � *F*_{2}) where δ ([*p*, *q*], *a*) = [δ_{1} (*p*, *a*), δ_{2} (*q*, *a*)]. But all the members of *Q*_{1} � *Q*_{2} may not necessarily represent reachable states of *M*. Hence, to reduce the amount of work, we start with a pair [*q*_{1}, *q*_{2}] and find transitions on every member of Σ from [*q*_{1}, *q*_{2}]. If some transitions go to a new pair, then we only generate that pair, because it will then represent a reachable state of *M*.

We next consider the newly generated pairs to find out the transitions from them. We continue this until no new pairs can be generated.

Let *M*_{1} = ( *Q*_{1}, Σ, δ_{1}, *q*_{1}, *F*_{1}) be a automata accepting *L*_{1}, and let *M*_{2} = (*Q*_{2}, Σ, δ_{2}, *q*_{2}, *F*_{2}) be a automata accepting *L*_{2}. *M* = (*Q*, Σ, δ, *q*_{0}, *F*) will be an automata accepting *L*_{1} ∩ *L*_{2}.

begin

*Q*_{old} = Φ
*Q*_{new} = { [ *q*_{1}, *q*_{2} ] }

While ( *Q*_{old} ≠ *Q*_{new} )

{

Temp = *Q*_{new} − *Q*_{old}
*Q*_{old} = *Q*_{new}
for every pair [*p*, *q*] in Temp do

for every a in Σ do

*Q*_{new} = *Q*_{new} ∪ δ ([*p*, *q* ], *a*)

}

*Q* = *Q*_{new}
end

Consider the automatas and their transition diagrams shown in Figure 3 and Figure 4.

The transition table for the automata accepting *L*(*M*_{1}) ∩ *L*(*M*_{2}) is:

We associate the names with states of the automata obtained, as shown below:

The transition table of the automata using the names associated above is: