2.2.4 Non-Deterministic FSAs

NON-DETERMINISTIC NFSA

Let's extend our discussion now to another class of FSAs: non-deterministic FSAs (or NFSAs). Consider the sheeptalk automaton in Figure 2.18, which is much like our first automaton in Figure 2.10:

Figure 2.18 A non-deterministic finite-state automaton for talking sheep (NFSA #1). Compare with the deterministic automaton in Fig. 2.10.

The only difference between this automaton and the previous one is that here in Figure 2.18 the self-loop is on state 2 instead of state 3. Consider using this network as an automaton for recognizing sheeptalk. When we get to state 2, if we see an a we don't know whether to remain in state 2 or go on to state 3. Automata with decision points like this are called non-deterministic FSAs (or NFSAs). Recall by contrast that Figure 2.10 specified a deterministic automaton, i.e., one whose behavior during recognition is fully determined by the state it is in and the symbol it is looking at. A deterministic automaton can be referred to as a DFSA. That is not true for the machine in Figure 2.18 (NFSA #1).

There is another common type of non-determinism, caused by arcs that have no symbols on them (called $ \varepsilon $-transitions). The automaton in Fig. 2.19 defines the exact

原书第 37 页

same language as the last one, or our first one, but it does it with an $ \varepsilon $-transition.

Figure 2.19 Another NFSA for the sheep language (NFSA #2). It differs from NFSA #1 in Fig. 2.18 in having an ε-transition.

We interpret this new arc as follows: If we are in state 3, we are allowed to move to state 2 without looking at the input, or advancing our input pointer. So this introduces another kind of non-determinism — we might not know whether to follow the $ \varepsilon $-transition or the ! arc.