Algorithms for Compiler Design: PROPERTIES OF REGULAR SETS

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.

Figure 1: Transition diagram.

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

Figure 2: Complement to transition diagram in Figure 1.

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₁ denotes the complement of L₁.

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

Therefore, if M₁ = (Q₁, Σ, δ₁, q₁, F₁) is an automata accepting L₁, and if M₂ = (Q₂, Σ, δ₂, q₂, F₂) is an automata accepting L₂, then the automata accepting L₁ ∩ L₂ will be: M = (Q₁ � Q₂, Σ, δ, [q₁, q₂], F₁ � F₂) where δ ([p, q], a) = [δ₁ (p, a), δ₂ (q, a)]. But all the members of Q₁ � Q₂ may not necessarily represent reachable states of M. Hence, to reduce the amount of work, we start with a pair [q₁, q₂] and find transitions on every member of Σ from [q₁, q₂]. 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₁ = ( Q₁, Σ, δ₁, q₁, F₁) be a automata accepting L₁, and let M₂ = (Q₂, Σ, δ₂, q₂, F₂) be a automata accepting L₂. M = (Q, Σ, δ, q₀, F) will be an automata accepting L₁ ∩ L₂.

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.

Figure 3: Transition diagram of automata M₁.

Figure 4: Transition diagram of automata M₂.

The transition table for the automata accepting L(M₁) ∩ L(M₂) is:

δ	A	b
[1, 1]	[1, 1]	[2, 4]
[2, 4]	[3, 3]	[4, 2]
[3, 3]	[2, 2]	[1, 1]
[4, 2]	[1, 1]	[2, 4]
[2, 2]	[3, 1]	[4, 4]
[3, 1]	[2, 1]	[1, 4]
[4, 4]	[1, 3]	[2, 2]
[2, 1]	[3, 1]	[4, 4]
[1, 4]*	[1, 3]	[2, 2]
[1, 3]	[1, 2]	[2, 1]
[1, 2]*	[1, 1]	[2, 4]

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

[1, 1]	A
[2, 4]	B
[3, 3]	C
[4, 2]	D
[2, 2]	E
[3, 1]	F
[4, 4]	G
[2, 1]	H
[1, 4]	I
[1, 3]	J
[1, 2]	K

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

δ	a	B
A	A	B
B	C	D
C	E	A
D	A	B
E	F	G
F	H	I
G	J	E
H	F	G
I*	J	E
J	K	H
K*	A	B