144 l;.l Theory of Computer Science
A
M 2
Fig. 5.7 NDFA accepting L(P + Q).
A
A
M 1
~
Fig. 5.8 NDFA accepting L(PQ).
Case 3 R = (P)*. In this case, qo, q and qt are introduced. New A-transitions
are introduced from qo to q, q to qr, q to the initial state of M] and from the
final states of M] to q. See Fig. 5.9.
Thus in all the cases. there exists an NDFA M with A-moves, accepting
the regular expression R with n + 1 characters. By the principle of induction.
this theorem is true for all regular expressions. I
A
A
qo ) - - - - - - J
l - - - - - - J G
Fig. 5.9 NDFA accepting L(P*).