1.9 CLOSURE PROPERTIES OF REGULAR LANGUAGES
THE O REM 1: If L 1 and L 2 are regular over Σ, then L
L
1
2
∪
is regular i.e.,
union of two regular sets is also regular. [Regular sets are closed w.r.t.
union].
Proof: As L 1 and L 2 are given to be regular; there exists finite automata
M
Q
q F
1
1
1
1
= ( , , , , )
Σ δ
and M
Q
q F
2
2
2
2
2
= ( , , , , )
Σ δ
such that L 1 = T(M 1 ) and
L 2 = T (M 2 ).
[ ( ) {
: ( , )
}
*
T M
x
q x F
= ∈
∈
Σ δ 0
is a lan guage L(M) accepted by M]
Let us assume that Q
Q
1
2
∩
= ∅.
Let us define NFA with ∈-transitions as follows:
M
Q
q F
3
0
= ( , , , , )
Σ δ
where
(i) Q Q
Q
q
=
∪
∪
1
2
0
{ } where q 0 is a new state not in Q
Q
1
2
∪
(ii) F F
F
=
∪
1
2
(iii) δ is defined by δ( , ) { , }
q
q q
0
1
2
∈ =
(a)
δ
δ
δ
( , )
( , )
( , )
q a
q a
q Q
q a
q Q
=
∈
∈
1
1
2
2
if
if
(b)
It is obvious that δ( , ) { , }
q
q q
0
1
2
∈ =
induces ∈-transitions either to the
initial state q 1 of M 1 or initial state q 2 of M 2 .
From (b), the transitions of M are the same as transitions M 1 or M 2
depending on whether q 1 or q 2 reached by ∈-transitions from q 0 .
Since F F
F
=
∪
1
2 , any string accepted by M 1 or M 2 accepted by M.
There fore L
L T M
1
2
∪ = ( ) and so is reg u lar.
¨
THE O REM 2: If L is regular and L ⊆ Σ
* , then Σ
*
− L is also a regular set.
Proof: Let L = T(M) where M
Q
q F
= ( , , , , )
Σ δ 0
is an FA.
Though L ⊆ Σ
* , δ (q, a) need not be defined as for all ‘a’ in Σ.
δ (q, a) is defined for some ‘a’ in Σ eventhough ‘a’ does not find a place in
the strings accepted by M.
Let us now modify Σ, Q and δ as defined below.
(i) If a ∈ −
Σ
Σ
1
, then the symbol ‘a’ will not appear in any string of
T(M). Therefore we delete ‘a’ from Σ 1 and all transitions defined
by the symbol ‘a’. T(M) is not affected by this).
(ii) If Σ Σ
−
≠ ∅
1
, we add a dead state d to Q. We define δ( , )
d a d
=
for all ‘a’ in Σ and δ( , )
d a d
= for all q in Q and ‘a’ in Σ Σ
− 1 .
Once again T(M) is not affected by this.
96
Theory of Automata, Formal Languages and Computation
THE O REM 1: If L 1 and L 2 are regular over Σ, then L
L
1
2
∪
is regular i.e.,
union of two regular sets is also regular. [Regular sets are closed w.r.t.
union].
Proof: As L 1 and L 2 are given to be regular; there exists finite automata
M
Q
q F
1
1
1
1
= ( , , , , )
Σ δ
and M
Q
q F
2
2
2
2
2
= ( , , , , )
Σ δ
such that L 1 = T(M 1 ) and
L 2 = T (M 2 ).
[ ( ) {
: ( , )
}
*
T M
x
q x F
= ∈
∈
Σ δ 0
is a lan guage L(M) accepted by M]
Let us assume that Q
Q
1
2
∩
= ∅.
Let us define NFA with ∈-transitions as follows:
M
Q
q F
3
0
= ( , , , , )
Σ δ
where
(i) Q Q
Q
q
=
∪
∪
1
2
0
{ } where q 0 is a new state not in Q
Q
1
2
∪
(ii) F F
F
=
∪
1
2
(iii) δ is defined by δ( , ) { , }
q
q q
0
1
2
∈ =
(a)
δ
δ
δ
( , )
( , )
( , )
q a
q a
q Q
q a
q Q
=
∈
∈
1
1
2
2
if
if
(b)
It is obvious that δ( , ) { , }
q
q q
0
1
2
∈ =
induces ∈-transitions either to the
initial state q 1 of M 1 or initial state q 2 of M 2 .
From (b), the transitions of M are the same as transitions M 1 or M 2
depending on whether q 1 or q 2 reached by ∈-transitions from q 0 .
Since F F
F
=
∪
1
2 , any string accepted by M 1 or M 2 accepted by M.
There fore L
L T M
1
2
∪ = ( ) and so is reg u lar.
¨
THE O REM 2: If L is regular and L ⊆ Σ
* , then Σ
*
− L is also a regular set.
Proof: Let L = T(M) where M
Q
q F
= ( , , , , )
Σ δ 0
is an FA.
Though L ⊆ Σ
* , δ (q, a) need not be defined as for all ‘a’ in Σ.
δ (q, a) is defined for some ‘a’ in Σ eventhough ‘a’ does not find a place in
the strings accepted by M.
Let us now modify Σ, Q and δ as defined below.
(i) If a ∈ −
Σ
Σ
1
, then the symbol ‘a’ will not appear in any string of
T(M). Therefore we delete ‘a’ from Σ 1 and all transitions defined
by the symbol ‘a’. T(M) is not affected by this).
(ii) If Σ Σ
−
≠ ∅
1
, we add a dead state d to Q. We define δ( , )
d a d
=
for all ‘a’ in Σ and δ( , )
d a d
= for all q in Q and ‘a’ in Σ Σ
− 1 .
Once again T(M) is not affected by this.
96
Theory of Automata, Formal Languages and Computation