Nondeterministic State Machines

All previous models (both fuzzy and crisp) are fully deterministic; for each state/input combination, it's clear what the next state should be. Nondeterminism enables us to define machines where more than one next state is defined for each situation. The model does not even specify which should be chosen; there doesn't necessarily need to be only one next state—all the specified options could be correct.

There is nothing uncertain about nondeterminism; there are no probabilities associated with transitions. Nondeterminism just reflects a lack of information about the next transition, essentially a gap in the formal definition. How we decide to deal with that is not a consequence of nondeterminism itself. Nondeterminism is just a less-explicit way of representing a state machine. In fact, most nondeterministic state machines are used in a deterministic fashion.

There can be two types of nondeterminism. One is nondeterminism in the transitions (present in automatons), the other is in the outputs (visible in transducers). The fact that no deterministic transition or outputs are specified is generally interpreted as, "Use an option that gives the correct answer." We'll discuss how to implement this in the next sections.

Definitions

Acceptors, recognizers, and transducers can be created with nondeterministic models.

Nondeterministic Finite-State Automaton

Formally, a nondeterministic finite-state automaton (NFSA) is defined in a similar way to a deterministic finite-state automaton. It's a quadruple:

Again, Q is the set of states including the start state q₀, F Q is the subset of accepting states, and S in the input alphabet. Only d is defined differently; it's a transition relation, which means there can be multiple transitions suggested. Formally speaking, it's not a one-to-one mapping from the current state and input symbol onto the next state.

A transition function is in fact a special case of a transition relation with at most one next state possible. To this extent, an FSA is a special case of an NFSA. So conceptually, the inputs and outputs are the same in both cases. In fact, we'll also show how a nondeterministic automaton can be converted to a deterministic one!

Nondeterministic Finite-State Machines

Both types of deterministic finite-state machines—Moore and Mealy—are also available in nondeterministic flavors. In both cases, the Moore machine is a simplified version of the Mealy machine, so the same differences about the output function apply; one is based on states, the other on transitions (see Chapter 38, "Finite-State Machines"). We'll study them both together this time.

The formal definition of a nondeterministic finite-state machine appears to be the same as the deterministic one:

Most terms are the same as for NFSA. Z is the output alphabet. However, again both d and l are in fact relations, and no longer functions. Let's look at the consequences of nondeterminism in both these relations:

• First, the transition relation d implies that multiple next states can be suggested for any state/input pair (q,s). In fact, no input is actually needed to trigger a transition (known as epsilon transitions e). This form of nondeterminism is the most common in both theory and practice.

• Second, for the output relation l, the symbol produced may vary based on the current state/input. This form of nondeterminism is not as common. In fact, l can often be interpreted as a deterministic function based on d. In this case, there is only one possible output per nondeterministic transition.

These changes in the definition also impose a few restrictions on the representation.

Representation

The data structures for finite-state machines were optimized to store only one transition per state/input pair. Nondeterminism does not guarantee this.

Problems with Arrays

Nondeterminism means that the standard array-based representation of the finite-state machines is no longer feasible. Indeed, many state/input cells in the array would require holding more than one value, as shown in Table 40.2. This would be necessary to represent all the transition and output options.

Table 40.2. An Array Attempting to Store the Transitions for a Nondeterministic Finite-State Machine (Some cells have more than one value.)

Input/State	1	2	3	4
a	2 & 4	-	-	-
b	-	3 & 4	-	-
e	- -		2	3

A somewhat inefficient solution to this would include a list of transitions for each cell. This overhead may be reduced by only having lists in the necessary cells, but a small flag would be needed to indicate whether the cell contains a list or a single value.

At this point, the array representation has lost its major advantage: simplicity. The efficiency of the lookup will also be reduced, so it would seem better to consider the graph-based approach.

Directed Graphs

The graph-based representation, as shown in Table 40.3, remains mostly unchanged by nondeterminism. The additional transitions needed to model the additional options can be added using the same representation. Only one additional type of transition is needed, the e transition to model the case where no input symbol is needed to trigger a transition.

Table 40.3. Using a Single Dimensional Array Storing Linked Lists to Represent the Same Nondeterministic Finite-State Machine

State	Transitions
1	a: 2, a: 4
2	b: 3, b: 4
3	e : 2
4	e : 3

This confirms the advantages of the graph-based representation. It will be needed to perform nondeterministic simulation of the state machine, or just to store it temporarily while it is converted to a deterministic model.

Algorithms

As mentioned, there are two ways to deal with nondeterminism. First, we can just simulate the machine in a way that is compatible with its nondeterministic definition (see Figure 40.2), putting up with the inconveniences and overheads (a recursive traversal that consumes memory exponentially). Second, we can decide to convert it to a deterministic finite-state machine, so we don't have the trouble of dealing with nondeterminism.

Nondeterministic Simulation

With standard finite-state machines, only one possible transition is applicable. This implies that the active state will change, but there will always be only one. With nondeterministic simulations, there may be more than one transition, which implies more than one active state.

Let's consider the algorithm with finite state automata first. It's simpler because no output is generated, and it's most common anyway. Start with a set of active states (usually just one), and read in the next symbol. If a transition from any of the current states matches, the corresponding next state is added to the next set of active states. This parallel simulation avoids backtracking (rewinding the input if we reach a dead end). Empty e transitions should be expanded immediately. This process continues reading in symbols and determining the next active states. If one of the states is an accepting state, the simulation ends.

For finite-state machines with deterministic outputs (but nondeterministic transitions), the algorithm needs to keep track of the output sequence for each of the active states. When a correct output sequence is detected, the simulation can stop.

In the case of nondeterministic outputs, things are even more complex. A set of the possible outputs needs to be maintained for each of the active states. This is quite cumbersome, and has little practical benefit, so it seems easier to use deterministic outputs.

Conversion to Deterministic

The procedure for creating a deterministic automaton from a nondeterministic one is known as the subset construction algorithm. Essentially, each state in the FSA is associated with a set of states in the NFSA. This is because of the fact that e transitions and ambiguous transitions may cause the same input string to reach different states in the NFSA (as in the simulation where multiple states can be active). So, during the construction, the corresponding subset of states in the NFSA is stored in each FSA state.

The algorithm starts with the e closure of the start states from the NFSA. This is the set of all states that can be reached from the start states by transition. Then, all the input symbols that can trigger a transition from this subset of states are considered. For each unique input symbol, one state in the FSA is created corresponding to the set of states in the NFSA that would be accessible with that input symbol. This set of states is stored along with the state of the FSA, so it can be expanded later. This process repeats until all the states of the FSA have been considered (see Listing 40.3).

Listing 40.3 Converting a Nondeterministic Finite-State Automaton to a Deterministic One Using a Subset of the Construction Algorithm

create the start state in the FSA
associate it with the subset of start states in the NFSA
while there is an unmarked state in the FSA
     scan the corresponding subset of NFSA states
     for each unique input that can trigger a transition
          find the corresponding subset of states in the NFSA
          create a new FSA state associated with this subset
          connect it the current state to this new one
     end for
     mark this state
end while

This same procedure can be applied to nondeterministic finite-state machines as long as the outputs are deterministic. If this is not the case, the final model cannot be made deterministic with this algorithm. It's best to resolve these problems manually or simulate the machine nondeterministically.

Discussion

Nondeterminism can simplify the process of creating FSA and finite-state machines. This is possible by using a less rigorous definition that allows multiple ambiguous transitions per input character, and e transition when no input characters are needed. For example, merging two finite state machines together (for instance, to combine and extend behaviors) can be done with a simple e transition between the appropriate states. An algorithm can then convert the most resulting finite-state machine to a deterministic one.

The simulation of nondeterministic machines can be slower, because the number of active states can potentially grow exponentially. Likewise, when converting nondeterministic finite-state automata into deterministic models, the number of total states can explode exponentially in the worst case—although that rarely happens in practice. Finally, nondeterministic output of finite-state machines is relatively awkward to handle, and generally ends up being exploited as a probabilistic finite-state machine.

The benefits of nondeterminism have not been identified by game developers, because they are never used in game AI. The major advantage lies in simplifying the modeling for the designer. Consider having to create an FSA to recognize enemies from teammates. It's often simpler to create two small FSA for each problem. An e transition can join the two together trivially. The result can be converted to a standard deterministic model for efficiency. Nondeterminism provides the best compromise between design simplicity and runtime efficiency. Another example would be to design the "replenish inventory" and "avoid combat" behaviors separately and use nondeterminism to combine these together.