A FSM, finite automaton, is a logical construct composed of
a set of states, a finite input token alphabet, and a transition function
to map states 
tokens to states.
According to Hopcroft and Ullman (1979),
a finite automaton is
formally denoted by
a 5-tuple (The transition function,,
,
,
, F), where
is a finite set of states,
is a finite input alphabet,
in
is the initial state,
is the set of final states, and
is the transition function mapping
. That is,
is a state for each state q and input symbol a.
, is defined as a set of 3-tuples
(
, a, 
) where 
is the current machine state,
a is an element of the token alphabet, and 
is the new machine state.
Table 3 formally defines the Hoshen-Kopelman finite state machine (FSM)
used in this study.
Table 3: Formal definition of the Hoshen-Kopelman finite state machine.
The FSM begins in 
and continues until a final state is
reached. The states in 
encapsulate
whether or not the west neighbor had been assigned a temporary cluster label
thereby eliminating the redundant analysis of the west neighbor.
Eliminating redundant conditionals increases the efficiency of the FSM implementation.
Table 4 is a working example of the FSM implementation
showing the formal state changes for one row of a sample map.
A description of
the FSM cluster identification (cluster_id) and the cluster relabeling (reLabel) source code is provided in Constantin (1995).
Table 4: Incremental state changes for the FSM working example.