arc labeled a will yield the same set of NFA states and thus get merged in the DFA.

Figure 2.17: Conversion of the NFA from Fig. 2,16 to a DFA

Example 2.15 : The construction of a DF.4. from the NFA of Fig. 2.16 is shown in Fig. 2.17. Each of the states of the DFA is located in the same position as the state p from which it is derived using rule (b) above. For example, consider the state 135, which is our shorthand for {1,3,5}. This state was constructed from state 3. It includes the start state, 1, because every set of the DFA states does. It also includes state 5 because that state is reached from state 1 by a suffix, e, of the string we that reaches state 3 in Fig. 2.16,

The transitions for each of the DFA states may be calculated according to the subset construction. However, the rule is simple. Fvom. any set of states that includes the start state qo and some other states {pi ,p2,--., P,j}, determine, for each symbol x, where the p,:s go in the NFA, and let this DFA state have a transition labeled x to the DFA state consisting of qo and all the targets of the

pis on symbol X. On all symbols x snch that there are no transitions out of any of the pis on symbol x, let this DFA state have a transition on x to that state of the DFA consisting of qo and all states that are reached from qo in the NFA following an arc labeled x.

For instance, consider state 135 of Fig. 2.17. The NFA of Fig. 2.16 has transitions on symbol b from .states 3 and 5 to states 4 and 6, respectively. Therefore, on symbol 6, 135 goes to 146. On symbol e, there are no transitions of the NF.A out of 3 or 5, but there is a transition from 1 to 5. Thus, in the DFA, 135 goes to 15 on input e. Similarly, on input w, 135 goes to 12.

On every otlier symbol x, there arc no transitions out or 3 or 5, and state 1 goes only to itself. Thus, there are transitions from 135 to 1 on every symbol in S other than 6, e. and v). We use the notation S-b-e-wto represent this set, and use similar representations of other sets in which a few symbols are removed from S. □

2.4.4 Exercises for Section 2.4

Exercise 2,4.1: Design NFAs to recognize the following sets of strings. * a) abc, abd, and aacd. Assume the alphabet is {a,b,c,d}.

b) 0101, 101, and Oil.

c) ab, be, and ca. Assume the alphabet is (o, 6, c}.

Exercise 2.4.2: Convert each of your NFAs from Exercise 2.4,1 to DFAs,

2.5 Finite Automata With Epsilon-Transitions

We shall now introduce another extension of the finite automaton. The new feature is that we allow a transition on e, the empty string. In effect, an NFA is allowed to make a transition spontaneously, without receiving an input symbol. Like the nondeterminism added in Section 2.3, this new capability does not expand the class of languages that can be accepted by finite automata, but it does give us some added programming convenience. We shall also see, when we take up regidar expressions in Section 3.1, how NFAs with e-transitions, which we call e-NFAs, are closely related to regular expressions and useful in proving the equivalence between the classes of languages accepted by finite automata and by regular expressions,

2.5.1 Uses of 6-Transitions

We shall begin with an informal treatment of e-NFAs, using transition diagrams with f. allowed as a label. In the examples to follow, think of the automaton as accepting those sequences of labels along paths from the start state to an accepting state. However, each e along a path is invisible ; i,e it contributes nothing to the string along the path.

Example 2.16: In Fig. 2.18 is an e-NFA that accepts decimal numbers consisting of:

1. An optional + or - sign,

2. A string of digits,

3. A decimal point, and

4. Another string of digits. Either this string of digits, or the string (2) can be empty, but at least one of the two strings of digits must be nonempty.

0,1.....9

0,1,...,9

Start

Figure 2.18: An c-NFA accepting decimal numbe:

Of particular interest is the transition from qu to qi on any of e, +, or -. Thus, state qi represents the situation in which we have seen the sign if there is orie, and perhaps some digits, but not the decimal point. State ga represents the .situation where we have just seen the decimal point, and may or may not have seen prior digits. In we have definitely seen at least one digit, but not the decimal point. Thus, the interpretation of 93 is that we have seen a decimal point and at least one digit, either before or after the decimal point. We may stay in 93 reading whatever digits there are, and also have the option of guessing the string of digits is complete and going spontaneously to q, the accepting state. □

Example 2.17: The strategy we outlined in Example 2.14 for building an NFA that recognizes a set of keywords can be simplified further if we allow e-transitions. For instance, the NFA recognizing the keywords web and ebay, which wc saw in Fig. 2,16, can also be implemented with e-transitions as in Fig. 2.19. Li general, we construct a complete sequence of states for each keyword, as if it w{;rc the only word the automaton needtid to recognize. Them, we add a new start state (state 9 in Fig. 2,19), with f-transitions to the start-states of the automata for each of the keywords. □