Chapter 5: Regular Sets and Regular Grammars ~ 167
The transition system M' is constructed as follows:
(i) The initial states of AI' are qo and qi'
(ii) The (only) final state of lvI' is qo.
(iii) The direction of the directed edges is reversed. M'is given in Fig. 5.30.
From (i)-(iii) it follows that
TUv!') = T(lUl
Hence. HM/ is regular.
o
0; ( ( a '
"0. 2 )
"-.../
Fig. 5.30 Finite automaton of T(M) r
Note: In Example 5.23. we can see by inspection that T(M') = {Ii 0
1
Ii.
j :2: O}. The strings of TiM') are obtained as path values of paths from qo to
itself or from qj to C/o.
Theorem 5.7 If L is a regular set over I. then I* - L is also regular over I.
Proof As L is regular by (viil. given at the end of Section 5.2.7, we can
construct a DFA fvl = (Q, I. 8. qo- F) accepting L. i.e. L = T(M).
We construct another DFA M' = (Q, I. 8. q!) r) by defining F' = Q - F,
i.e. ,'v! and M' differ only in their final states. A final state of [1,1' is a nonfinal
state of 1' 1' 1 and vice versa. The state diagrams of M and M' are the same except
for the final states.
t\" E HM') if and only if D(C/o. H) E r = Q - F. i.e. iff t\" eo L. This
pre-yes TUv1') = I'" - X. I
Theorem 5.8 If X and Yare regular sets over I, then X n Y is also regular
over I.
Proof By DeMorgan' s Im\ for sets. X n Y =I'" - ((I'" - Xl u (I* - Y). By
Theorem 5.7. ~> - X and I* - Yare regular. So. (I* - Xl u (2:* - Y) is
also regular. By applying Theorem 5.7. once agam 2:* - ((I* - X, u
(I* - Y)) is regular. i.e. )( n Y is regular. I
5.6 REGULAR SETS AND REGULAR GRAMMARS
We have seen that regular sets are precisely those accepted by DFA. In this
section we show that the class of regular sets over 2: is precisely the regular
languages mer the terminal set I.