THEOREM 1: If L1 and L2 are regular over S, then L1 L2 È is regular i.e., union of two regular sets is also regular. [Regular sets are closed w.r.t. union].
Proof: As L1 and L2 are given to be regular; there exists finite automata M1 Q 1 q1 F1 = ( , S,d , , ) and M2 Q2 2 q2 F2 = ( , S,d , , ) such that
L1 = T(M1) and
L2 = T (M2).
[T (M) = {x ÎS* : d(q , x)ÎF} is a language L(M) accepted by M]
Let us assume that Q1 ÇQ2 = Æ.
Let us define NFA with Î-transitions as follows:
M3 Q q0 F = ( , S,d, , )
where
It is obvious that d(q0 , ) {q1 , q2} Î = induces Î-transitions either to the initial state q1 of M1 or initial state q2 of M2.
From (b), the transitions of M are the same as transitions M1 or M2 depending on whether q1 or q2 reached by Î-transitions from q0.
Since F = F È F 1 2, any string accepted by M1 or M2 accepted by M. Therefore L1 L2 T M È = ( ) and so is reg ular. ¨
THEOREM 2: If L is regular and L Í S* , then S* - L is also a regular set.
Proof: Let L = T(M) where M = (Q, S,d, q , F ) 0 is an FA.
Though L Í S*, d (q, a) need not be defined as for all ‘a’ in S. d (q, a) is defined for some ‘a’ in S even though ‘a’ does not find a place in the strings accepted by M.
Let us now modify S, Q and d as defined below.
Once again T (M) is not affected by this.
Let us consider M got after applying (i) and (ii) to S,Q and d. We write the modified M as
(Q, S, d, q , F ).
Let us now define a new automaton M¢ by
M¢ = (Q, S,d, q ,Q - F ) 0 .
We can see that wÎT (M¢ ) iff d(q0 , w) Q F Î - and wÏT (M).
Therefore S* - L = T (M¢ ) and therefore regular.
THEOREM 3: If L1 and L2 are regular, so is L1 L2 Ç [Regular sets are closed w.r.t. Intersection]
Proof: It is important to note that
If L1 and L2 are regular, then Lc1, Lc2are regular by theorem 1.
Therefore is regular by theorem 2.
Hence L1 ÇL2is regular.