Finite-state Machine - Mathematical Model

Mathematical Model

In accordance with the general classification, the following formal definitions are found:

• A deterministic finite state machine or acceptor deterministic finite state machine is a quintuple, where:
  • is the input alphabet (a finite, non-empty set of symbols).
  • is a finite, non-empty set of states.
  • is an initial state, an element of .
  • is the state-transition function: (in a nondeterministic finite automaton it would be, i.e., would return a set of states).
  • is the set of final states, a (possibly empty) subset of .

For both deterministic and non-deterministic FSMs, it is conventional to allow to be a partial function, i.e. does not have to be defined for every combination of and . If an FSM is in a state, the next symbol is and is not defined, then can announce an error (i.e. reject the input). This is useful in definitions of general state machines, but less useful when transforming the machine. Some algorithms in their default form may require total functions.

A finite-state machine is a restricted Turing machine where the head can only perform "read" operations, and always moves from left to right.

• A finite state transducer is a sextuple, where:
  • is the input alphabet (a finite non empty set of symbols).
  • is the output alphabet (a finite, non-empty set of symbols).
  • is a finite, non-empty set of states.
  • is the initial state, an element of . In a nondeterministic finite automaton, is a set of initial states.
  • is the state-transition function: .
  • is the output function.

If the output function is a function of a state and input alphabet that definition corresponds to the Mealy model, and can be modelled as a Mealy machine. If the output function depends only on a state that definition corresponds to the Moore model, and can be modelled as a Moore machine. A finite-state machine with no output function at all is known as a semiautomaton or transition system.

If we disregard the first output symbol of a Moore machine, then it can be readily converted to an output-equivalent Mealy machine by setting the output function of every Mealy transition (i.e. labeling every edge) with the output symbol given of the destination Moore state. The converse transformation is less straightforward because a Mealy machine state may have different output labels on its incoming transitions (edges). Every such state needs to be split in multiple Moore machine states, one for every incident output symbol.