40 FINITE AUTOMATA
For instance, in the above example,
~-closure({!lo)> = {Qo, Ql},
~-closure({qa}) = {Ql, 42}*Now, we extend the transition function 6 to the domain 2Q x (C U {E}) by
S(A, a) = E-closure (
qE E-closure( A)and then further extend it to the domain 2Q x C* as follows:
w4 4 = e-closure (A),
S(A, za) = S(S(A, x), a), if x E C* and a E C.For instance, in the above example, we have s((qo},O) = {ql,a2}, and
6((w 421, 1) = {qr,q2}. Therefore, s((qo},Ol) = (al,q2}. Note that
s({qo}, 2) is the set of all leaves in all computation paths of CC.
We can now formally define that an NFA A4 = (Q, C, S, ~0, F) accepts input
x if s((qo}, z) n F # (8. For an NFA M, we let L(M) denote the set of all
strings accepted by M; that isL(M) = {z E c* I q(ao},z) n F # 0).
It is often easier to design NFA’s than DFA’s. The following are some
examples.Example 2.17 Find an NFA that accepts the set of binary strings having a
substring 010.Solution. We show the NFA M in Figure 2.19. Note that it is just the checker
for substring 010 plus two loops from state 40 to 40 with labels 0 and 1. These
two loops allow the machine to wait until it successfully checks the substring
- With these two waiting loops, we do not need to define S(ql,O) = ql and
6(q2,1) = 40, as we did in a DFA. Instead, we simply let s(41,O) = S(q2,l) = 8.
We also show, in Figure 2.20, the computation tree of A4 on input CC = - Note that there are two occurrences of 010 in IX: and so there are two
different accepting paths for X. cl
Figure 2.19: NFA for Example 2.17.