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 is a five-tuple where
is a state machine (or semiautomaton),
is a non-empty set whose elements are called output symbols, and
is a function called the output function.
The sets and are generally considered to be finite. In the literature, a finite state-output machine is also known as transducer.
is complete if and ; otherwise, it is incomplete;
is sequential if and .
Both and can be extended so its first component takes on a set of states:
Note that for any input symbol .
Words as Input
The transition and the output functions of a state-output machine are defined to work only over individual symbols in as inputs. However, finite strings of symbols over , or words, are usually fed to the , instead of individual symbols. Therefore, we would like modify and in order to handle finite strings as well.
- Extending .
When a machine receives an input word , it reads 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 is at state upon receiving , we define a next state as a state that enters after reading the last symbol of .
Based on the above discussion, we are ready to extend so it takes on words over . This is done inductively:
, where is the empty word, and is any state;
, where and .
It is easy to see that .
- Extending .
There are in general two ways to view output(s) for a given input word:
The first, more common, approach, is to view outputs as being produced after the last symbol of the input word is processed:
, where is a word over .
If does not depend on input symbols, say for all , the above definition may be modified so that non-empty output(s) may be produced by the empty input word :
, where is any word over .
It is easy to see that . Note that this is not a true extension of the original output function, because the new output function now depends on inputs.
Alternatively, outputs may be produced each time a transition occurs. In other words, outputs are words over . Thus, outputs are inductively as follows:
, where is the empty word, and
, where and .
When there is no confusion, we may continue to denote and as the extensions of the original next-state and output functions.
Given , define an input configuration as a pair for some and , and an output configuration as a pair for some and . The set of output configurations for a given input configuration is given by .
Generator and Acceptor
One may treat a state-output machine 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:
- as a generator.
Fix a non-empty set of starting states, and a non-empty set . The triple is called a generator. A string is generated by if for some . The set of all strings generated by is also denoted by .
- as an acceptor.
Dually, fix a non-empty set called the final states, and a non-empty set . The triple is called an acceptor. A string is said to be accepted by if and for some state . The set of all strings accepted by is denoted by .
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).
|Date of creation||2013-03-22 18:59:49|
|Last modified on||2013-03-22 18:59:49|
|Last modified by||CWoo (3771)|