  In this paper we develop an analogue of the graph-theoretic `modular
decomposition' in automata theory. This decomposition allows us to identify
hierarchical finite state machines (HFSMs) equivalent to a given finite state
machine (FSM). We first define a module of an FSM, which is a collection of
nodes which can be treated as a nested FSM. We then identify a natural subset
of FSM modules called thin modules, which are algebraically well-behaved. We
construct a linear-space directed graph, which uniquely represents every thin
module, and hence every equivalent (thin) HFSM. We call this graph the modular
decomposition. The modular decomposition makes clear the significant common
structure underlying equivalent HFSMs, and allows us to efficiently construct
equivalent HFSMs. Finally, we provide an $O(n^2k)$ algorithm for constructing
the modular decomposition of an $n$-state $k$-symbol FSM.
