sequential machine

views updated

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,q0 |→ q1,x b,q1 |→ q1,y c,q1 |→ q2,z

Then, if the machine is in state q0 and reads a, it moves to state q1 and outputs x, and so on. Assuming the starting state to be q0, 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 fQ from I × Q to Q and an output function fO 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 fO(b,q1) = y

whereas fO(c,q1) = 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.