Formal Definitions

Although the concepts at the base of each category of finite-state system are similar, there are different definitions for finite-state automata, Mealy, and Moore machines.

Finite-State Automatons

Finite-state automata (FSA) are a computational model, often used as recognizers or acceptors (see Figure 38.1). Intuitively, the entire input sequence allows the automaton to output the corresponding class or a Boolean (if the pattern was recognized or accepted, respectively). For example, an FSA could be used to recognize the actions look down, fire rocket, and jump as a rocket jump. FSA could also categorize enemies or friends based on their behavior. (For instance, fire twice is accepted as an enemy.)

Figure 38.1. Graphical representation of a finite-state automaton used for accepting and recognizing input patterns. On the left, the sequence abccca is accepted. On the right, the sequence bbbb is recognized as category Y.

Essentially, an FSA consists of a set of states connected together by transitions. Because it is provided with a data stream, the active state changes if a transition matches the input character. After all the characters have been consumed, the current active state can determine whether a pattern was recognizable.

More formally, a finite-state automaton can be considered a quadruple:

Q is the set of states, and d is the transition function defined over an input alphabet S. There is one particular state: the start state q₀, where the computation begins. There's a special subset of states F Q known as terminal (or accepting) states. Each of these concepts is now explained in greater depth.

Input Alphabet

The finite-state automaton is fed a stream of data. Each element in this data stream can be understood as a specific character, taken from a finite alphabet S (see Table 38.1).

Table 38.1. Some Examples of Input Sequences and the Corresponding Input Alphabet

Sequence	Alphabet
0010001000110	S1={0,1}
Abbabcbabbacc	S2={a,b,c,d}
Flash shout explosion smoke	S2 set of in-game events

In the first case, the alphabet S₁ has two characters corresponding to on and off bits. The second string has characters from the alphabet S₂ consisting of the first four letters, although d is not present in the string. Although it's easier to discuss these ideas with letters, each of them can be substituted to game events, such as jump, fire projectile, drop weapon, and so on.

The role of the finite-state automaton is to process the characters from this input stream one by one. This allows computations to be performed. For example, the patterns in the data can be identified and classified as necessary.

States

A state can be understood as a node from a graph. Because same states have a particular meaning for the problem, they are assigned names as well as identifiers (which are more intuitive to work with).

In FSA, some states have a special meaning. One state, denoted q₀, is active in the initial configuration of the finite-state automaton (for instance, assume neutral player). It is generally denoted by a bold circle in graphical representations. There are also some accepting states, called F, which usually contain a class type (for instance, decide friend or foe). These are double circles.

Table 38.2. All the States in a Finite-State Machine, Along with Their Different Properties (Class, Terminal, and State)

State	Terminal	Class
1*	No
2	Yes	X
3	No
4	Yes	Y
Start state is denoted with an asterisk.

If the pattern causes the finite-state automaton to finish with one of these states active, the pattern is recognized as the corresponding class.

Transition Function

The transition function determines the next active state q_t+1 based on the current state q₁, and the input character s_t. (The subscript t denotes the index in the sequence.) Mathematically, it can be modeled as a function mapping the set of states and the input alphabet onto the set of states:

The transition function essentially changes the internal state of the finite-state automaton based on the input patterns. Graphically, transitions can be modeled as directed connections between two nodes in a graph (see Figure 38.2 and Table 38.3).

Figure 38.2. The example finite-state automata in graphical form.

Table 38.3. Transition Table Containing the Start and End of Each Transition and the Input Character Required, Corresponding to the FSA in Figure 38.2

Start State	Character	End State
1	a	4
1	b	3
2	b	1
3	c	2
4	a	1

Each transition is triggered by a particular character in the input stream. The transition is said to consume the character; this is indicated in the graph by writing the character near the transition. Strictly speaking, all connections (including recurrent ones) need to be expressed by the transition function. However, often it's easier to assume the state stays the same if there are no applicable outbound links.

Mealy Machines

Finite-state machines unlike the automata just discussed produce an output while the input stream is processed. Mealy machines (named after their inventor) output symbols based on each transition. Mealy machines can be understood as a superset of FSA that dispose of more flexibility. They are better suited to sequential control problems (for instance, to provide a response action for each comment of the enemy).

Accordingly, there is a different definition for what a Mealy finite-state machine is a quintuple this time:

Just like for finite-state automata, S represents the set of characters in the input alphabet, Q is the set of states, and d is the transition function. Now for the new ones: Z is another set representing the output alphabet, and l is a function to determine the output based on the transitions. We'll look into these new concepts a bit further.

Output Alphabet

At each step t of the simulation, a Mealy finite-state machine can output a symbol. Each symbol belongs to the output alphabet, which can be animat actions, as shown in Table 38.4.

Table 38.4. A Collection of Output Sequences and the Corresponding Output Alphabet

Sequence	Set
000101010111	S1={0,1}
eggheheif	S2={e,f,g,h,i}
jump shoot crouch	S3 set of animat actions

There is absolutely no correlation between input and output alphabets. They can be different sizes and contain different symbols.

The role of the state machine is to produce a sequence of output symbols based on the input pattern. The output at every step t of the simulation may not always be necessary, but it's almost just as easy for the finite-state machine to compute it regardless!

Output Function

In practice, the output is computed by another function. This is done in a fashion similar to the state transition, using a function mapping the current state and the input symbol onto the output value:

Because the transition and output functions are defined over the same set, they can be represented in the same way. Graphically, this means it's possible to attach an output symbol to each link in the directed graph (see Figure 38.3).

Figure 38.3. Finite-state machines produce output on each transition. The output is noted alongside the input character consumed, in the input/output order.

To output a symbol every step while a state remains active, it is necessary to have a recurrent connection. Although this proves the most flexible approach, this is not always the most elegant way to proceed.

Moore Machines

Moore machines provide a simpler alternative to finite-state machines. Instead of outputting symbols for each transition, the states determine output. The formal definition of a Moore machine is the same as a Mealy machine, although the output function l is simpler but less powerful. These are used more often because they are easier to design for game AI.

In this case, the transition function can be expressed in much simpler terms, mapping the current state onto the output:

This has repercussions on the graphical representation, too. Instead of writing the output near the transitions, they can be displayed within each state, as shown in Figure 38.4.

Figure 38.4. Moore machines have an output value associated with each state rather than the transition.

As a nice consequence of this, we no longer need to explicitly model recurrent connections; the output will remain the same while no external transition is taken.