sequential machine

sequential machine
1. A finite-state automaton with output (in some contexts including machines with infinite state set). Thus there is a function f from the Cartesian product I × Q to the product Q × O, with Q a set of states and I, O finite sets of input and output symbols respectively. Suppose, for example, a,q₀ |→ q₁,x b,q₁ |→ q₁,y c,q₁ |→ q₂,z

Then, if the machine is in state q₀ and reads a, it moves to state q₁ and outputs x, and so on. Assuming the starting state to be q₀, it can be seen for example that the input string abbbc is mapped to the output string xyyyz. This mapping from the set of all input strings to the set of all output strings, i.e. I* to O*, is called the response function of the machine. The function f comprises a state-transition function f_Q from I × Q to Q and an output function f_O from I × Q to O.

What is described here is sometimes called a Mealy machine to distinguish it from the more restricted Moore machines. In a Moore machine, the symbol output at each stage depends only on the current state, and not on the input symbol read. The example above is therefore not a Moore machine since f_O(b,q₁) = y

whereas f_O(c,q₁) = z

Any Moore machine can be converted to an equivalent Mealy machine by adding more states.

A generalized sequential machine is an extension of the notion of sequential machine: a string of symbols is output at each stage rather than a single symbol. Thus there is a function from I × Q to Q × O*. See also gsm mapping.

2. Another name for sequential circuit.