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 (, , , ,TheF), where is a finite set ofstates, is a finiteinput alphabet, in is theinitial state, is the set offinal states, and is thetransition functionmapping . That is, is a state for each stateqand input symbola.

**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.

Michael W. Berry (berry@cs.utk.edu)

Sat Mar 30 23:40:13 EST 1996