produces a DFA with 2 - 8 states, corresponding to all the subsets of these three states. Figure 2.12 shows the transition table for these eight states; we shall show shortly the details of how some of these entries are computed.

Notice that this transition table belongs to a deterministic finite automaton. Even though tlie entries in the table are sets, the states of the constructed DFA are sets. To make the point clearer, we can invent new names for these states, e.g., A for 0, В for {o}, and so on. The DFA transition table of Fig 2.13 defines exactly the same automaton as Fig. 2.12. but makes clear the point that the entries in the tabic arc single states of the DFA.

Figure 2.13; Renaming the states of Fig. 2.12

Of the eight states in Fig. 2.13, starting in the start state B, we can only reach states B, E, and F. The other five states are inaccessible from the start state and may as well not be there. We often can avoid the exponential-time step of constructing transition-table entries for every subset of states if we perform lazy evaluation on the subsets, as follows.

BASIS: We know for certain that the singleton set consisting only of As start state is a<;eessible.

INDUCTION: Suppose we have determined that set S of states is accessible. Then for each input symbol a, compute the set of states 6n{S, a); we know that tiiese sets of states will also be accessible.

For the example at hand, we know that {qa} is a state of the DFA D. We find that Soiiqoj.O) - {go,gi} and Sn{{qo}A) = {qo}- Both these facts are established by looking at the transition diagram of Fig. 2.9 and observing that on 0 there are arcs out of qo to both go and q\, while on 1 there is an arc only to go. We thus have one row of the transition table for the DFA: the second row in Fig. 2.12.

One of the two sets we computed is old ; {o} has already been considered. However, the other - {go> <dfi} - is пелу and its transitions must be computed. We find 5D({go,gi},0) {go,gi} and 6n{{qo>4i},) = {jcga}- For instance, to see the latter calculation, we know that

(o{{9o,<Jl}, 1) <>N{qo, 1) и йл-(91,1) = {9o} и {дз} - {9о,9э}

We now have the fifth row of Fig. 2.12, and we have discovered on(; new state of D, which is {9o:?2}- A similar calculation tells us

D({5o,9a},0) = 5jyi{qa,0) U 5лг((/2,0) = {qo>qi] U 0 {goQi} Ь((9о, 92), 1) = -5/v(9o, 1) и 3(2,1) = Ы и 0 = {<?и}

These calculations give us the sixth row of Fig. 2.12, but it gives us only sets of states that we have already seen.

Thus, the subset construction has converged; we know all the a<;cessible states and their transitions. The entire DFA is shown in Fig. 2.14. Notice that it has only three states, which is, by coincidence, exactly the same number of states as the NFA of Fig. 2.9, frorn which it was constructed. However, the DFA of Fig, 2.14 has six transitions, compared with the four transitions in Fig. 2,9. □

Start

Figure 2,14: The DFA constructed from the NFA of Fig 2.9

We need to show formally that the subset construction works, although the intuition was suggested by the examples. .After reading sequence of input symbols Ш, the constructed DFA is in one state that is the set of NFA states that the NFA would be in after reading w. Since the accepting states of the DFA are those sets that include at least one accepting state of the NF.A, and the NFA also accepts if it gets uito at least one of its accepting states, we may then conclude that the DFA and NF,4 accept exactly the same strings, and therefore accept the same language.

Theorem 2.11: If D = {Qn,,5v,{(}n},FD) is the DFA constructed from NFA = {Олг,2,5л,9о, F] by the subset construction, then L{D) = /.(AO-PROOF: What we actually prove first, by induction on ;, is that

Notice that each of the 5 functions returns a set of states from Qj\, but So interprets this set as one of the states of (which is the power set of QaO: while 6n interprets this set as a subset of Qn-

(2.4)

Thus, Equations (2.2) and (2.4) demonstrate that л({до),ги) = 6!{qo,w). When we observe that D and both accept w if and only if Sn{{qo},4) or Jv(goiWJ), respectively, contain a state in Fjv, we have a complete proof that L{D) = L{N). a

Theorem 2.12: A language L is accepted by some DFA if and only if L is accepted by some NFA.

PROOF: (If) The if part is the subset construction and Theorem 2.11.

(Only-if) This part is easy; we have only to convert a DFA into an identical NFA. Put intuitively, if we have the transition diagram for a DFA, we can also interpret it as the transition diagram of an NFA, which happens to have exactly one choice of transition in any situation. More formally, let D = {Q.,Y:,6D,(i(>,F) be a DFA. Define Л = iQ,T 6i\f,qo,F) to be the equivalent NFA, where 6; is defined by the rule:

If So{q,a) = p, then S!{q,a) - {p}.

It is then easy to show by induction on that if Snigo, w) = p then

V(go,w) = {p}

We leave the proof to the reader. As a consequence, w is accepted by D if and only if it is accepted by N; i.e., L(D) - L{N). □

BASIS: Let \w\ = 0; that is, w = e. By the basis definitions of б for DFAs and NFAs, both 6d{{Qo},} and йлг(до,е) are {qo}.

INDUCTION: Let w be of length n + 1, and assume the statement for length n. Break ш up as w - xa, where a is the final symbol of w. By the inductive hypothesis, SnUqo},) = ж(до,ж). Let both these sets of As states be

The inductive part of the definition of 5 for NFAs tells us

SNiqo,w}= [JSiv(pt,a) (2.2)

The subset construction, on the other hand, tells us that

SDi{pi,P2,---,Pk},a) = [JSN(Pi,a) (2.3)

Now, let us use (2.3) and the fact that S£){{qo},x) - {pi,p-i,- ,Pk} in the inductive part of the definition of § for DFAs: