stateoutput machine
Definition
A stateoutput machine can be thought of as state machine with an output feature: when a word is fed into the machine as input, the machine goes through a series of internal “states” where certain translations take place, and finally a set of words are produced as outputs.
Formally, a stateoutput machine $M$ is a fivetuple $(S,\mathrm{\Sigma},\mathrm{\Delta},\delta ,\lambda )$ where

1.
$(S,\mathrm{\Sigma},\delta )$ is a state machine (or semiautomaton),

2.
$\mathrm{\Delta}$ is a nonempty set whose elements are called output symbols, and

3.
$\lambda :S\times \mathrm{\Sigma}\to P(\mathrm{\Delta})$ is a function called the output function.
The sets $S,\mathrm{\Sigma},$ and $\mathrm{\Delta}$ are generally considered to be finite. In the literature, a finite stateoutput machine is also known as transducer.
Note that there is no restrictions^{} on the sizes of $\lambda (s,a)$ and $\delta (s,a)$. Various classifications based on the cardinalities of $\lambda (s,a)$ and $\delta (s,a)$ are possible: for all $(s,a)\in S\times \mathrm{\Sigma}$,

•
$M$ is complete^{} if $\lambda (s,a)\ge 1$ and $\delta (s,a)\ge 1$; otherwise, it is incomplete;

•
$M$ is sequential if $\lambda (s,a)\le 1$ and $\delta (s,a)\le 1$.
Both $\delta $ and $\lambda $ can be extended so its first component^{} takes on a set $T$ of states:
$$\delta (T,a):=\bigcup \{\delta (t,a)\mid t\in T\}\mathit{\hspace{1em}\hspace{1em}}\text{and}\mathit{\hspace{1em}\hspace{1em}}\lambda (T,a):=\bigcup \{\lambda (t,a)\mid t\in T\}.$$ 
Note that $\delta (\mathrm{\varnothing},a)=\lambda (\mathrm{\varnothing},a)=\mathrm{\varnothing}$ for any input symbol $a\in \mathrm{\Sigma}$.
Words as Input
The transition and the output functions of a stateoutput machine $M$ are defined to work only over individual symbols in $\mathrm{\Sigma}$ as inputs. However, finite strings of symbols over $\mathrm{\Sigma}$, or words, are usually fed to the $M$, instead of individual symbols. Therefore, we would like modify $\delta $ and $\lambda $ in order to handle finite strings as well.
 Extending $\delta $.

When a machine $M$ receives an input word $u$, it reads $u$ one symbol at a time, starting from the left, until the last symbol is read. After reading each symbol, the machine goes into a next state, dictated by the transition function $\delta $. If $M$ is at state $s$ upon receiving $u$, we define a next state as a state that $M$ enters after reading the last symbol of $u$.
Based on the above discussion, we are ready to extend $\delta $ so it takes on words over $\mathrm{\Sigma}$. This is done inductively:

–
${\delta}^{\prime}(s,\u03f5):=\{s\}$, where $\u03f5$ is the empty word^{}, and $s$ is any state;

–
${\delta}^{\prime}(s,ua):=\delta ({\delta}^{\prime}(s,u),a)$, where $a\in \mathrm{\Sigma}$ and $u\in {\mathrm{\Sigma}}^{*}$.
It is easy to see that ${\delta}^{\prime}(s,uv)={\delta}^{\prime}({\delta}^{\prime}(s,u),v)$.

–
 Extending $\lambda $.

There are in general two ways to view output(s) for a given input word:

(a)
The first, more common, approach, is to view outputs as being produced after the last symbol of the input word is processed:

*
${\lambda}^{\prime}(s,\u03f5):=\mathrm{\varnothing}$, and

*
${\lambda}^{\prime}(s,ua):=\lambda ({\delta}^{\prime}(s,u),a)$, where $u$ is a word over $\mathrm{\Sigma}$.
If $\lambda $ does not depend on input symbols, say $\lambda (s,a)=\beta (s)$ for all $(s,a)\in S\times \mathrm{\Sigma}$, the above definition may be modified so that nonempty output(s) may be produced by the empty input word $\u03f5$:

*
${\lambda}^{\prime}(s,u):=\beta ({\delta}^{\prime}(s,u))$, where $u$ is any word over $\mathrm{\Sigma}$.
It is easy to see that $\lambda (s,\u03f5)=\beta (s)$. Note that this is not a true extension^{} of the original output function, because the new output function now depends on inputs.

*

(b)
Alternatively, outputs may be produced each time a transition occurs. In other words, outputs are words over $\mathrm{\Delta}$. Thus, outputs are inductively as follows:

*
${\lambda}^{\prime}(s,\u03f5):=\{\u03f5\}$, where $\u03f5$ is the empty word, and

*
${\lambda}^{\prime}(s,ua):={\lambda}^{\prime}(s,u)\lambda ({\delta}^{\prime}(s,u),a)$, where $a\in \mathrm{\Sigma}$ and $u\in {\mathrm{\Sigma}}^{*}$.

*

(a)
When there is no confusion, we may continue to denote $\lambda $ and $\delta $ as the extensions of the original nextstate and output functions.
Given $M$, define an input configuration^{} as a pair $(s,u)$ for some $s\in S$ and $u\in {\mathrm{\Sigma}}^{*}$, and an output configuration as a pair $(t,v)$ for some $t\in S$ and $v\in {\mathrm{\Delta}}^{*}$. The set of output configurations for a given input configuration $(s,u)$ is given by $\delta (s,u)\times \lambda (s,u)$.
Generator and Acceptor
One may treat a stateoutput machine $M=(S,\mathrm{\Sigma},\mathrm{\Delta},\delta ,\lambda )$ as either a language^{} generator^{} or a language acceptor. The idea is that a set of states and a set of words need to be specified as initial conditions, so that words can either be generated or accepted from these initial conditions. The way this works is as follows:
 $M$ as a generator.

Fix a nonempty set $I\subseteq S$ of starting states, and a nonempty set $G\subseteq {\mathrm{\Sigma}}^{*}$. The triple $(M,I,G)$ is called a generator. A string $b\in {\mathrm{\Delta}}^{*}$ is generated by $(M,I,G)$ if $b\in \lambda (s,a)$ for some $(s,a)\in I\times G$. The set of all strings generated by $(M,I,G)$ is also denoted by $L(M,I,G)$.
A typical example of a generator is a Post system: a state machine where the output alphabet is the input alphabet, and the set of states and the state function is suppressed ($S$ may be taken as a singleton).
 $M$ as an acceptor.

Dually, fix a nonempty set $F\subseteq S$ called the final states, and a nonempty set $A\subseteq {\mathrm{\Delta}}^{*}$. The triple $(M,F,A)$ is called an acceptor. A string $a\in {\mathrm{\Sigma}}^{*}$ is said to be accepted by $(M,F,A)$ if $\delta (s,a)\in F$ and $\lambda (s,a)\in A$ for some state $s\in S$. The set of all strings accepted by $(M,F,A)$ is denoted by $L(M,F,A)$.
A typical example of an acceptor is an automaton: a state machine where the output alphabet and the output function are not essential (${\mathrm{\Delta}}^{*}$ may be taken as a singleton).
Remark. Observe that the functions $\delta $ and $\lambda $ can be combined to form a single function $\tau :S\times \mathrm{\Sigma}\to P(S)\times P(\mathrm{\Delta})$ such that $\tau =(\delta ,\lambda )$. One can generalize this so that $\tau $ is a function from $S\times \mathrm{\Sigma}$ to $P(S\times \mathrm{\Delta})$, or more generally, to $P(S\times {\mathrm{\Delta}}^{*})$. The resulting construct is commonly known as a generalized sequential machine.
References
 1 S. Ginsburg, An Introduction to Mathematical Machine Theory, AddisionWesley, (1962).
 2 M. Arbib, Algebraic Theory of Machines, Languages, and Semigroups^{}, Academic Press, (1968).
 3 J. Hartmanis, R.E. Stearns, Algebraic Structure^{} Theory of Sequential Machines, PrenticeHall, (1966).
Title  stateoutput machine 
Canonical name  StateoutputMachine 
Date of creation  20130322 18:59:49 
Last modified on  20130322 18:59:49 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  14 
Author  CWoo (3771) 
Entry type  Definition 
Classification  msc 03D05 
Classification  msc 68Q45 
Related topic  GeneralizedSequentialMachine 
Related topic  Semiautomaton 
Defines  sequential machine 
Defines  complete machine 
Defines  incomplete machine 