You are here
Homegeneralized sequential machine
Primary tabs
generalized sequential machine
Definition
Generalized sequential machines are generalizations of finite state sequential machines. In a finite state machine $M=(S,\Sigma,\Delta,\delta,\lambda)$, the nextstate ($\delta$) and output ($\lambda$) functions work independently of one another in the sense that no next states affect the outputs, and vice versa: given an input symbol $a$ and current state $s$, if $p,q$ are next states, and $c,d$ are output symbols, then all four output configurations are possible: $(p,c),(p,d),(q,c),(q,d)$. In addition, for a given input symbol $a$, the corresponding outputs are individual symbols in the output alphabet, rather than words: $\lambda(s,a)$ is a subset of $\Delta$. When these restrictions are removed, we have a generalized sequential machine.
Formally, a generalized sequential machine is a quadruple $M=(S,\Sigma,\Delta,\tau)$, such that
1. $S$ is an alphabet whose elements are called states,
2. $\Sigma$ is an alphabet whose elements are called input symbols,
3. $\Delta$ is an alphabet whose elements are called output symbols, and
4. $\tau$ is a function from $S\times\Sigma$ to $P(S\times\Delta^{*})$, such that $\tau(s,a)$ is finite for all $(s,a)\in S\times\Sigma$. $\tau$ is called the transition function.
A generalized sequential machine is also called a gsm for short. Note that a gsm $M$ becomes a finite state machine if $\tau$ can be written as $(\delta,\lambda)$, and $\lambda$ is a function from $S\times\Sigma$ to $P(\Delta)$. A gsm is said to be deterministic if each $\tau(s,a)$ is a singleton. So a Mealy machine is just a deterministic gsm such that $\tau(s,a)$ consists of an output symbol.
Like a finite state machine, the function $\tau$ can be extended so its first component applies to sets of states, rather than individual states:
$\tau(T,a)=\bigcup\{\tau(s,a)\mid s\in T\}.$ 
As usual, $\tau(\varnothing,a)=\varnothing$.
Next, we can extend $\tau$ so $M$ can process input words rather than input symbols. The key idea, like in the case of a fsm, is that the input word is processed one symbol at a time from left to right. Each time an input symbol is processed or consumed, a set of output configurations are produced. The states in these output configurations are used to process the next input symbols, and the outputs are appended to the right of the outputs that have already been generated. More precisely,
$\tau(T,ua):=\{(s,vw)\mid(s,w)\in\tau(t,a)\mbox{ for some }t\in S\mbox{ such % that }(t,v)\in\tau(T,u)\}.$ 
When the input word is the empty word $\lambda$, we require its output to be the empty word also, without changing the state, hence $\tau(s,\lambda):=\{(s,\lambda)\}$.
Here’s an example. Let $M=(\{s,t\},\{a,b\},\{c,d\},\tau)$ be a gsm whose transition function $\tau$ is given by the following table
$(x,y)$  $\tau(x,y)$ 

$(s,a)$  $\{(t,c)\}$ 
$(s,b)$  $\{(s,cd),(s,d^{2})\}$ 
$(t,a)$  $\{(t,dc)\}$ 
$(t,b)$  $\{(s,d),(s,c^{2})\}$ 
To fine $\tau(s,ab)$, first find $\tau(s,a)$, which consists of a single output configuration $(t,c)$ according to the table above. So $c$ will serve as the prefix of the output(s). The next state is now $t$, to be applied to the second symbol $b$ in $ab$. By the table above, $\tau(t,b)$ has two output configurations: $(s,d)$ and $(s,c^{2})$. Therefore, the final output configurations are $(s,cd)$ and $(s,c^{3})$, when $c$ is appended to the left of $d$ and $c^{2}$. We may also apply the formula above:
$\displaystyle\tau(s,ab)$  $\displaystyle=$  $\displaystyle\{(p,vw)\mid(p,w)\in\tau(q,b)\mbox{ where }(q,v)\in\tau(s,a)\}$  
$\displaystyle=$  $\displaystyle\{(p,cw)\mid(p,w)\in\tau(t,b)\}$  
$\displaystyle=$  $\displaystyle\{(s,cd),(s,c^{3})\}.$ 
Language Translation
A gsm can be used to translate languages. In other words, an input language $L$ over $\Sigma$ is fed into a gsm $M$ so that an output language $M(L)$ is produced, or “translated”. This can be done by fixing a start state $s_{0}$ and a set $F$ of final states, much like an automaton. First, consider an input word $u$, then $\tau(s_{0},u)$ is the resulting set of output configurations. Define the set of outputs translated from $u$ by $M$ as:
$\operatorname{GSM}_{M}(u):=\{v\mid(t,v)\in\tau(s_{0},u)\mbox{ for some }t\in F\}.$ 
More generally, let $L$ be an input language (a set of inputs), define the output language translated from $L$ by $M$ as:
$\operatorname{GSM}_{M}(L):=\{v\mid v\in\operatorname{GSM}(u)\mbox{ for some }u% \in L\}.$ 
It is clear that $\operatorname{GSM}_{M}$ is a mapping from $P(\Sigma^{*})$ to $P(\Delta^{*})$, and it is in this regard that we see $M$ as a language translator. Of course, different start states and different sets of final states produce different translations, which is the reason why a gsm is usually regarded as a 6tuple $(S,\Sigma,\Delta,\tau,s_{0},F)$ rather than a quadruple.
Given a set $K$ of output words, one can ask the inverse question: what are all the input words whose output configurations contain an output word in $K$? In other words, we are forming the set:
$\operatorname{GSM}^{{1}}_{M}(K):=\{u\mid\operatorname{GSM}_{M}(u)\cap K\neq% \varnothing\}.$ 
Note, however, that if $L=\operatorname{GSM}^{{1}}_{M}(K)$, then $L$ in general does not get translated to $K$: the function $\operatorname{GSM}^{{1}}_{M}$ is not a functional inverse of $\operatorname{GSM}_{M}$:
$\operatorname{GSM}_{M}\circ\operatorname{GSM}^{{1}}_{M}(K)\neq K\qquad\mbox{% and}\qquad\operatorname{GSM}_{M}^{{1}}\circ\operatorname{GSM}_{M}(L)\neq L$ 
in general.
GSM as an Acceptor
A gsm may be turned into a language acceptor in the following way: let $M=(S,\Sigma,\Delta,\tau,s_{0},F)$ be a gsm with starting state $s_{0}$ and $F$ the set of final states. Then the language
$L(M):=\{u\in\Sigma^{*}\mid\operatorname{GSM}(u)\neq\varnothing\}$ 
is called the language accepted by M. Now, given $M$, we may construct a gsm $M^{{\prime}}=(S,\Sigma,\varnothing,\tau^{{\prime}},s_{0},F)$, such that $\tau^{{\prime}}(s,a):=\{(t,\epsilon)\mid(t,v)\in\tau(s,a)\mbox{ for some }v\in% \Delta^{*}\}$, where $\epsilon$ denotes the empty word. It is easy to see that $L(M)=L(M^{{\prime}})$. Given any $(s,a)\in S\times\Sigma$, define $s\to at$ iff $(t,\epsilon)\in\tau^{{\prime}}(s,a)$. From this, it is readily seen that the formal grammar $G=(\Sigma\cup S,F,P,s_{0})$, where the productions in $P$ are of the form $s\to at$ defined earlier, generates $L(M^{{\prime}})$. As a result, every language accepted by a gsm is regular. It is not hard to see that the converse is also true: every regular language is accepted by some gsm.
GSM Mappings
The gsm mapping of a gsm $M$ is the function $\operatorname{GSM}_{M}:P(\Sigma^{*})\to P(\Delta^{*})$ defined earlier. A GSM mapping is a function $\operatorname{GSM}_{M}$ for some gsm $M$. An inverse GSM mapping is defined similarly. A GSM mapping is said to be $\lambda$free if $(t,\epsilon)\notin\tau(s,a)$ for any $(s,a)\in S\times\Sigma$.
Examples

Any language homomorphism is a gsm mapping. Given a homomorphism $h:\Sigma\to\Delta^{*}$, define $M=(S,\Sigma,\Delta,\tau,s_{0},F)$ such that $S=F=\{s_{0}\}$ and $\tau(s_{0},a)=\{(s_{0},h(a))\}$. Then $M$ is a gsm with $\operatorname{GSM}_{M}=h$. Similarly, any inverse homomorphism is an inverse gsm mapping.

The mapping $L\mapsto L\cap R$, where $R$ is a regular language, is a gsm mapping. To see this, let $G$ be a grammar generating $R$ consisting of productions of the form $A\to aB$ or the form $A\to\lambda$. Define $M=(S,\Sigma,\Sigma,\tau,s_{0},F)$ as follows: $S$ consists of the nonterminals of $G$ as well as a new symbol $s$, $s_{0}$ is the starting symbol for $G$, and $F=\{s\}$. Next, set $\tau(A,a)=(B,a)$ iff $A\to aB$, and $\tau(A,a)=(s,a)$ iff $A\to\lambda$. Then, for any word $u$, it is easy to see that $\operatorname{GSM}_{M}(u)=\{u\}$ iff $u\in R$. As a result, $\operatorname{GSM}_{M}(L)=L\cap R$.
A family $\mathscr{F}$ of languages is said to be closed under GSM mappings if for any $L\in\mathscr{F}$, $\operatorname{GSM}_{M}(L)\in\mathscr{F}$ for any gsm $M$. Closure under $\lambda$free GSM mappings and inverse GSM mappings are similarly defined. It can be shown that each of the four families in the Chomsky hierarchy is closed under inverse GSM mappings. While the families of regular, contextfree, and T0 languages are closed under GSM mappings, the family of contextsensitive languages is only closed under $\lambda$free GSM mappings.
References
 1 A. Salomaa, Formal Languages, Academic Press, New York (1973).
 2 J.E. Hopcroft, J.D. Ullman, Formal Languages and Their Relation to Automata, AddisonWesley, (1969).
Mathematics Subject Classification
03D05 no label found68Q45 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections