# 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*_{0} |→ *q*_{1},*x* *b*,*q*_{1} |→ *q*_{1},*y* *c*,*q*_{1} |→ *q*_{2},*z*

Then, if the machine is in state *q*_{0} and reads *a*, it moves to state *q*_{1} and outputs *x*, and so on. Assuming the starting state to be *q*_{0}, 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*_{1}) = *y*

whereas *f*_{O}(*c*,*q*_{1}) = *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.

#### More From encyclopedia.com

#### You Might Also Like

#### NEARBY TERMS

**sequential machine**