3. 5{qa, 00) = S{qo, 0) и S{qj, 0) - {</o, ?i } U 0 = {90, 9i }

4. 5{go,001) = 6{qo, 1) и Siqi, 1) - {qo} U {93} = {?o, <?2}-

5. (go,0010) = SiqcQ) U <5(g2:0) = {qo,qi} U 0 = {90,1}.

6. %o, 00101) = S(qo, 1) и 5(91,1) = {Яо} U {92} = {90,92).

Line (1) is the basis rule. We obtain line (2) by applying 6 to the lone state, 90, that is in the previous set, and get {90,91} as a result. Line (3) is obtained by taking the union over the two states in the previous set of what we get when wo apply 5 to them with input 0, That is, (90,0) = {go,9i}, while S{qi.,0) = 0. For line (4), we take the union of (90,1) = {qo} and (91,1) - {92}- Lines (5) and (6) are similar to lines (3) and (4), О

2.ЗА The Language of an NFA

As we have suggested, an NFA accepts a string w if it is possible to make any sequence of choices of next state, while readuig the characters of ш, and go from the start state to any accepting state. The fact that other choices using the input symbols of w lead to a nonaccepting state, or do not lead to any state at all (i.e., the sequence of states dies ), does not prevent w from being accepted by the NFA as a whole. Formally, li A = (Q,£,d,9o,F) is an NFA, then

L(.4)-{u>%o, )nF0}

That is, L{A) is the set of strings w in S* such that d{qo,w) contains at least one accepting state.

Example 2.9: As an example, let us prove formally that the NFA of Fig. 2.9 accepts the language L = {w\w ends in 01}. The proof is a mutual induction of the following three statements that characterize the three states:

1. (90, contains 9o for every w.

2. 5(90, w] contains 91 if and only if w ends in 0.

3. 5(90, w) contains 92 if and only if ги ends in 01.

To prove these statements, we need to consider how A can reach each state; i.e., what was the la,st input symbol, and in what state was A just before reading that symbol?

Since the language of this automaton is the set of strings w such that S{qo,w) contains 93 (because 92 is the only accepting state), the proof of these three statements, in particular the proof of (3), guarantees that the language of this NFA is the set of strings ending in 01. The proof of the theorem is an induction on \w\, the length oi w, starting with length 0.

BASIS: If = 0, then w = e. Statement (1) says that S{qo.,e} contains go, which it does by the basis part of the definition of 6. For statement (2), we know that € does not end in 0, and we also know that (o, e) does not contain (/1, again l)y the basis part of the definition of 5. Thus, the hypotheses of both directions of the if-and-only-if statement are false, and therefore both directions of the statement are true. The proof of statement (3) for yj = e is essentially the same as the above proof for statement (2).

INDUCTION: Assume that w - xa, where a is a symbol, either 0 or 1, We may assume statements (1) through (3) hold for x, and we need to prove them for w. That is, we assume \ui\ - n + 1, so x = n. We assume the inductive hypothesis for n and prove it for n -f-1.

1, We know that 5{qo, x) contains qn Since there are transitions on both 0 and 1 from qo to itself, it follows that S(qo,w) also contains qo, so statement (1) is proved for w.

2, (If) Assume that lu ends in 0; i.e., a - 0. By statement (1) applied to x, we know that S{qo,x) contains qo. Since there is a transition from go to qi nn input 0, we conclude that 5{qQ, w) contains qi.

(Only-if) Suppose 5(9о,ш) contains q\. If we look at the diagram of Fig. 2.9, we see that the only way to get into state q\ is if the input sequence w is of the form rcO. That is enough to prove the only-if portion of statement (2).

3, (If) .4ssume that w ends in 01. Then if = жа, we know that a = 1 and X ends in 0. By statement (2) apphed to x, we know that Ь{([о,х) contains q\. Since there is a transition from 51 to 92 on input 1, we conclude that S(qo,w) contains 92-

(Only-if) Suppose 6{qo,w} contains 92- Looking at the diagram of Fig. 2.9, we discover that the only way to get to state q- is for w to be of the form :rl, where 5(01) contains q. By statement (2) applied to x, we know that X ends in 0. Thus, w ends in 01, and we have proved statement (3).

□

2.3.5 Equivalence of Deterministic and Nondeterministic Finite Automata

Although there are many languages for which an NFA is easier to construct than a DFA, such as the language (Example 2.6) of strings that end in 01, it is a surprising fact that every language that can be described by some NFA can also be described by some DFA. Moreover, the DFA in practice has about as many states as the NFA, although it often has more transitions. Ln the worst case, however, the smallest DFA can have 2 states while the smallest NFA for the same language has only n states.

The proof that DFAs can do whatever NFAs can do involves an important construction called the subset construction because it involves constructing all subsets of the set of states of the NFA, In general, many proofs about automata involve constructing one automaton from another. It is important for us to observe the subset construction as an example of how one formally describes one automaton in terms of the states and transitions of another, without knowing the specifics of the latter automaton.

The subset construction starts from an NFA N = {Qn,,Sn,4q,F!). Its goal is the description of a DFA D = {Qd,S Sd, {<io}, Fd) such that L[D) = L{N). Notice that the input alphabets of the two automata are the same, and the start state of D is the set containing only the start state of N. The other components of D are constructed as follows.

Qd is the set of subsets of Qat; i.e., Qd is the power set of Q/v- Note that if Qi has n states, then Qn will have 2 states. Often, not all these states are accessible from the start state oi Qd- Inaccessible states can be thrown away, so effectively, the number of states of D may be much smaller than 2 ,

Fo is the set of subsets S of Qn such that, S П Fn ф That is, Fb is all sets of JVs states that include at least one a<;cepting state of N.

For each set S CQ and for each input symbol о in E,

SD{S,a) = и 6Nip., a)

p in S

That is, to compute 5n{S,a) we look at all the states p in 5, see what states N goes to from p on Input c, and take the union of all those states.

Figure 2.12: The complete subset construction from Fig. 2,9

Example 2.10: Let iV be the automaton of Fig. 2.9 that accepts all strings that end in 01. Since Ns set of states is {90-91,92}, the subset construction