state-output machine

Definition

A state-output 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 state-output machine $M$ is a five-tuple $(S,\mathrm{\Sigma },\mathrm{\Delta },\delta ,\lambda )$ where

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

2. $\mathrm{\Delta }$ is a non-empty 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 state-output 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 state-output 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,ϵ):=\{s\}$, where $ϵ$ 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:

1. 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,ϵ):=\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 non-empty output(s) may be produced by the empty input word $ϵ$:

   • ${\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,ϵ)=\beta (s)$. Note that this is not a true extension of the original output function, because the new output function now depends on inputs.

2. 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,ϵ):=\{ϵ\}$, where $ϵ$ 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 }}^{*}$.

When there is no confusion, we may continue to denote $\lambda$ and $\delta$ as the extensions of the original next-state 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 state-output 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 non-empty set $I\subseteq S$ of starting states, and a non-empty 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 non-empty set $F\subseteq S$ called the final states, and a non-empty 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.

Title	state-output machine
Canonical name	StateoutputMachine
Date of creation	2013-03-22 18:59:49
Last modified on	2013-03-22 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