State Machines

State Machines

Overview

Next: [Transducer State Machines]

State machines in general, and transducer state machines in particular, are tools which should be in progrmmers' toolboxes.

A state machine may be defined in several ways.

A deterministic finite state machine may be defined mathematically by a quintuple (Σ, S, s0, δ, F), where:

• Σ is the input alphabet (a finite, non-empty set of symbols).

• S is a finite, non-empty set of states.
• s0 is an initial state, an element of S.
• δ is the state-transition function: δ: S x Σ → S.
• F is the set of final states, a (possibly empty) subset of S.
  (State machine op. cit. (en.wikipedia.org))

To be more specific about an aspect of a state machine so defined, the state transition function δ may be a partial function. A complete function δ would define a transition for every symbol in every state. A partial function δ defines only some transitions. In some states, some symbols would make no sense, or would be undefined. Such transitions may remain undefined, and if that particular symbol is received while in that particular state, an error may be emitted, or the symbol may simply be silently ignored.

A state machine may be defined functionally as a machine which reads a series of symbols in the input alphabet Σ. When it reads an input symbol it will switch to a different state based solely on that input symbol and the current state. Each state is associated with a set of transitions which specify the state to switch to for a given input symbol (ibid. (en.wikipedia.org)). A state machine as described here may be used to parse text to determine if it meets a criterion or not. In this case, the text, made up of the characters from the standard alphabet as symbols, is supplied to the state machine, which operates on the input symbols until it reaches one of the final states indicating the outcome of the parsing.

A state machine may be defined programmatically as a computer program which includes two parts. A first part assembles user data defining the structure of a state machine. This data includes data representing an input alphabet Σ, a set of states S, an initial state s0, and a set of final states F. This part of the program generates a data structure containing this information. A second part defines and implements the transition function δ. The second part then receives input data representing the input symbols. This part accesses the previously generated data structure to determine the next state and transitions to that state.

State machines can be a perfect solution to some control problems. For example, if the response to a received symbol is different at different times or under different circumstances, a standard program can end up containing a complicated arrangement of ifs and elses. However, it is possible that a simple state machine may be designed to provide the necessary control.

There is much more information available on state machines in general from the mathematical and theoretical to the practical.

Next: [Transducer State Machines]