* Compute (5(go,5.) as follows:

1. First compute <5(gi, .)\jS{qi, .) = {<]>} U {q) = {q.q-}.

2. Then compute

<5(go,5.) ECLOSE(g2}UKCLOSE(g3) - {92} U {93.45} = {Qi-qs.q.}

Compute Д(9о,5.6) as follows:

1. First compute Ця-2,6) U 6(93,6) U S(q,6) = {93} U {9:4} U 0 = {93}-

2. Then compute S{qo,5.6) = ECl-0SE(9:t) = {93,9.i}

Now, we can define the language of an f-NF.\ E = (Q.T,.6,qa. F) in the expected way: L{E) = {w й(9о.и>) П F ф Щ. That is, the language of E is the set of strings u that take the start state to at least one accepting state. For instance, we saw in Example 2.20 that 6(90,5.6) coiUains the accepting state 95, so the string 5,6 is in the language of that <-NF.A.

2.5.5 Eliminating f-Transitions

Given any e-NF.\ E, we can find a DFA D that acc(>ptti the same language a,s E. The construction we use is very close to the subset construction, as the states of D are subsets of the states of E. The only difference is that wr mu.st incorporate e-transitions of E, whitJi we do through the mechanLsm of the f-clnsure. Let £ = (Q/;,5],dE,9o,FE). Then the etiuivalent DFA

is defined as follows:

1. Qn is the set of subsets of Qf.:. More precisely, we shall find that all accessible states of D are (-dosed subsets of Qe-, tliai is, sets S С Qi.-such that 5 - ECLOSE(5). Put another wa}-, the f-closed .s *(,s of states S are those such that any f-trausition out of one of the states in 5 leads (o a state that is also in S. Note that 0 is an f-closed set,

2. 9D = ECl.OSE(9o); that is, wc get the start state of D l>y closing the sc>t consistmg of only the start state of E. Note that this rule differs from the original subset construction, where the st<u-t state of the constructed automaton WEis.just the set containing the start state of the given NF.A,

3. Fo is those sets of states that contain at least one accepting state of E. That is, Fd = {S\S is in Qo and 5 П F/. 0}.

4. 6о{3,а) is computed, for ail n in S and sets S in Qn by:

(a) Let S = {pi,P2,---,Pk}-

(b) Compute Ui eIpuu); let this set be {г1,Г2,.. .,Гт}.

(c) Then SoiSa) - U Li ECLOSE(rj).

Example 2.21: Let us eliminate e-transitions from the e-NFA of Fig. 2.18, which we shall call E in what follows. From E, we construct an DFA D, which is shown in Fig. 2.22. How-ever, to avoid clutter, we omitted from Fig. 2.22 the dead state 0 and all transitions to the dead state. You should imagine that for each state shown in Fig. 2.22 there are additional transitions from any state to 0 on any input symbols for which a transition is not indicated. Also, the state 0 has transitions to itself on all input symbols.

0,1,...,9

0,1,...,9

0,1,...,9

0,1,.,.,9

Figure 2,22: The DFA D that eliminates e-transitions from Fig. 2.18

Since the start state of E is go, the start state of D is Eclose(qo); which is {go,gi}- Our first job is to find the successors of and qi on the various symbols hi E; note that these symbols are the plus and minus signs, the dot, and the digits 0 through 9. On + and -. Qx goes nowhere in Fig, 2,18, while qo goes to q\. Thus, to compute Sniiqo-.gi]-, +) we start with {qi] and e-close it. Since there are no e-transitions out of gi, we have ({go,gi},+) - {qi}-Similarly, Su{{qo,qi}; -) - {qi}- These two transitions are shown by one arc in Fig, 2,22,

Next, we need to compute Sp{{qo,qi}, .), Since go goes nowhere on the dot, and gi goes to g2 in Fig. 2.18, we must e-close {дг}- As there are no e-transitions out of g2, this state is its own closure, so 5с({до,gi}, ) = {г}-

Finally, we must compute fD({go, ?! }i 0), as an example of the transitions from {go, gi} on all the digits. We find that go goes nowhere on the digits, but qi goes to both gi and 94. Since neither of those states have e-transitions out, we conclude Sn{{qo, gi}, 0) = {дь g<i}, and fikewise for the other digits.

We have now explained the arcs out of {goii} in Fig, 2.22. The other transitions are computed similarly, and we leave them for you to check. Since 95 is the only accepting state of E, the accepting states of D are those accessible states that contain 95. We see these two sets {93,95} and {92,93,95} indicated by double circles in Fig. 2.22, □

Theorem 2.22: A language L is accepted by some e-NFA if and only if L is accepted by some DFA.

PROOF: (If) This direction is easy. Suppose L = L{D) for some DF.A. Turn D into an e-DFA E by adding transitions 5{q,e) - 0 for all states q of D. Technically, we must also convert the transitions of D on input symbols, e.g., Sniq-.a) - P into an NFA-transition to the set containing only p, that is Eiq-.a) - {p}. Thus, the transitions of E and D are the same, but E explicitly states that there are no transitions out of any state on e.

(Ordy-if) Let E = (Qfi, S, (Se, 90, б) be an e-NFA. Apply the modified subset construction described above to produce the DFA

We need to show that L{D) = L{E), and we do so by showing that the extended transition functions of E and D are the same. Formally, we show SE{qo,w) - oiUDiw) by induction on the length of w.

BASIS: If li - 0, then w = t. We know &E{чo) - ECLOSE(<7o). We also know that qn - eclose(9o), because that is how the start state of D is defined. Finally, for a DFA, we know that ((p, () - p for any state p, so in particular, d{qD,f-) = eclose(9o). We have thus proved that 6е{чоу) = 6oiQD,e).

INDUCTION: Suppose w = xa, where a is the final symbol of №, and assume that the .statement holds for x. That is, (o,-) = oiqa)- Let both these sets of states be {pi,p2, - ,Pk}-

By the definition of 6 for e-NFAs, we compute SEiqaw) by:

1. Let {г,Г2,...,Гт} be Uf=i

2. Then 5e(9o,w) = U 1 ECLOSE(jj).

If we examine the construction of DFA D in the modified subset construction above, we see that &d[{p\;P2,- .pk}-,o) is constructed by the same two steps (1) and (2) above. Thus, Si:){qo,w), лvhicb is 5d{{pitP2,- - чР/;},о) is the same set as Зе{Яо, We have now proved that Sjiqo, w) - Sniqo, u-} and completed the inductive part. □