Chapter 5: Regular Sets and Regular Grammars ~ 143
Basis. Let the number of characters in R be 1. Then R =A, or R = 0, or
R =ai, ai E I. The transition systems given in Fig. 5.5 will recognize these
regular expressions.
-O~~
R =A
R =$
R =8 i
Fig. 5.5 Transition systems for recognizing elementary regular sets.
Induction step. Assume that the theorem is true for regular expressions having
n characters. Let R be a regular expression having 11 + 1 characters. Then,
R=P+Q
or
R = PQ
or
R = p*
according as the last operator in R is +, product or closure. Also P and Q are
regular expressions having 11 characters or less. By induction hypothesis. L(P)
and L(Q) are recognized by M j and M: where M 1 and M: are NDFAs with
A-moves, such that L(P) = T(M j ) and L(Q) = T(M:). M j and M: are
represented in Fig. 5.6.
r
o
01
o
o
Fig. 5.6 Nondeterministic finite automata M 1 and M 2 .
The initial state and the final states of M j and M: are represented in the usual
way.
Case 1 R =P + Q. In this case we construct an NDFA M with A-moves
that accepts L(P + Q) as fo11O\'/s: qo is the initial state of M, qo not in M j
or M:. qj is the final state of M: once again q( not in M j or M:. M contains
all the states of M, and M: and also their transitions. We add additional
A-transitions from qo to the initial states of M 1 and M: and from the final
states of M j and M: to qt. The NDFA M is as in Fig. 5.7. It is easy to see
that TUI1) = T(MJ u T(M 2 ) = L(P + Q).
Case 2 R =PQ. In this case we introduce qo as the initial state of M and
qr as the final state of M. both qo, qr not in M] or M 2 . New A-transitions are
added between qo and the initial state of M j • between final states of M j and
the initial state of M 2 • and between final states of M: and the final state qr of
M. See Fig. 5.8.