state-output machine


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,Σ,Δ,δ,λ) where

  1. 1.

    (S,Σ,δ) is a state machine (or semiautomaton),

  2. 2.

    Δ is a non-empty set whose elements are called output symbols, and

  3. 3.

    λ:S×ΣP(Δ) is a function called the output function.

The sets S,Σ, and Δ are generally considered to be finite. In the literature, a finite state-output machine is also known as transducer.

Note that there is no restrictionsPlanetmathPlanetmathPlanetmathPlanetmath on the sizes of λ(s,a) and δ(s,a). Various classifications based on the cardinalities of λ(s,a) and δ(s,a) are possible: for all (s,a)S×Σ,

  • M is completePlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath if |λ(s,a)|1 and |δ(s,a)|1; otherwise, it is incomplete;

  • M is sequential if |λ(s,a)|1 and |δ(s,a)|1.

Both δ and λ can be extended so its first componentMathworldPlanetmath takes on a set T of states:

δ(T,a):={δ(t,a)tT}  and  λ(T,a):={λ(t,a)tT}.

Note that δ(,a)=λ(,a)= for any input symbol aΣ.

Words as Input

The transition and the output functions of a state-output machine M are defined to work only over individual symbols in Σ as inputs. However, finite strings of symbols over Σ, or words, are usually fed to the M, instead of individual symbols. Therefore, we would like modify δ and λ in order to handle finite strings as well.

Extending δ.

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 δ. 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 δ so it takes on words over Σ. This is done inductively:

  • δ(s,ϵ):={s}, where ϵ is the empty wordPlanetmathPlanetmathPlanetmath, and s is any state;

  • δ(s,ua):=δ(δ(s,u),a), where aΣ and uΣ*.

It is easy to see that δ(s,uv)=δ(δ(s,u),v).

Extending λ.

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

  1. (a)

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

    • *

      λ(s,ϵ):=, and

    • *

      λ(s,ua):=λ(δ(s,u),a), where u is a word over Σ.

    If λ does not depend on input symbols, say λ(s,a)=β(s) for all (s,a)S×Σ, the above definition may be modified so that non-empty output(s) may be produced by the empty input word ϵ:

    • *

      λ(s,u):=β(δ(s,u)), where u is any word over Σ.

    It is easy to see that λ(s,ϵ)=β(s). Note that this is not a true extensionPlanetmathPlanetmathPlanetmath of the original output function, because the new output function now depends on inputs.

  2. (b)

    Alternatively, outputs may be produced each time a transition occurs. In other words, outputs are words over Δ. Thus, outputs are inductively as follows:

    • *

      λ(s,ϵ):={ϵ}, where ϵ is the empty word, and

    • *

      λ(s,ua):=λ(s,u)λ(δ(s,u),a), where aΣ and uΣ*.

When there is no confusion, we may continue to denote λ and δ as the extensions of the original next-state and output functions.

Given M, define an input configurationMathworldPlanetmath as a pair (s,u) for some sS and uΣ*, and an output configuration as a pair (t,v) for some tS and vΔ*. The set of output configurations for a given input configuration (s,u) is given by δ(s,u)×λ(s,u).

Generator and Acceptor

One may treat a state-output machine M=(S,Σ,Δ,δ,λ) as either a languagePlanetmathPlanetmath generatorPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath 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 IS of starting states, and a non-empty set GΣ*. The triple (M,I,G) is called a generator. A string bΔ* is generated by (M,I,G) if bλ(s,a) for some (s,a)I×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 FS called the final states, and a non-empty set AΔ*. The triple (M,F,A) is called an acceptor. A string aΣ* is said to be accepted by (M,F,A) if δ(s,a)F and λ(s,a)A for some state sS. 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 (Δ* may be taken as a singleton).

Remark. Observe that the functions δ and λ can be combined to form a single function τ:S×ΣP(S)×P(Δ) such that τ=(δ,λ). One can generalize this so that τ is a function from S×Σ to P(S×Δ), or more generally, to P(S×Δ*). The resulting construct is commonly known as a generalized sequential machine.


  • 1 S. Ginsburg, An Introduction to Mathematical Machine Theory, Addision-Wesley, (1962).
  • 2 M. Arbib, Algebraic Theory of Machines, Languages, and SemigroupsPlanetmathPlanetmath, Academic Press, (1968).
  • 3 J. Hartmanis, R.E. Stearns, Algebraic StructurePlanetmathPlanetmath Theory of Sequential Machines, Prentice-Hall, (1966).
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