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 L1 denotes the complement of L1.
An automata for accepting L1 ∩ L2 is required in order to simulate the moves of an automata that accepts L1 as well as the moves of an automata that accepts L2 on the input string x. Hence, every state of the automata that accepts L1 ∩ L2 will be an ordered pair [p, q], where p is a state of the automata accepting L1 and q is a state of the automata accepting L2.
Therefore, if M1 = (Q1, Σ, δ1, q1, F1) is an automata accepting L1, and if M2 = (Q2, Σ, δ2, q2, F2) is an automata accepting L2, then the automata accepting L1 ∩ L2 will be: M = (Q1 � Q2, Σ, δ, [q1, q2], F1 � F2) where δ ([p, q], a) = [δ1 (p, a), δ2 (q, a)]. But all the members of Q1 � Q2 may not necessarily represent reachable states of M. Hence, to reduce the amount of work, we start with a pair [q1, q2] and find transitions on every member of Σ from [q1, q2]. 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 M1 = ( Q1, Σ, δ1, q1, F1) be a automata accepting L1, and let M2 = (Q2, Σ, δ2, q2, F2) be a automata accepting L2. M = (Q, Σ, δ, q0, F) will be an automata accepting L1 ∩ L2.
begin
Qold = Φ
Qnew = { [ q1, q2 ] }
While ( Qold ≠ Qnew )
{
Temp = Qnew − Qold
Qold = Qnew
for every pair [p, q] in Temp do
for every a in Σ do
Qnew = Qnew ∪ δ ([p, q ], a)
}
Q = Qnew
end
Consider the automatas and their transition diagrams shown in Figure 3 and Figure 4.
The transition table for the automata accepting L(M1) ∩ L(M2) 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:
