Generalised Stream X-Machines and Cooperating Distributed Grammar Systems |
| |
Authors: | Marian Gheorghe |
| |
Affiliation: | (1) Department of Computer Science, Sheffield University, Sheffield, UK, GB |
| |
Abstract: | Stream X-machines are a general and powerful computational model. By coupling the control structure of a stream X-machine
with a set of formal grammars a new machine called a generalised stream X-machine with underlying distributed grammars, acting as a translator, is obtained. By introducing this new mechanism a hierarchy of computational models is provided.
If the grammars are of a particular class, say regular or context-free, then finite sets are translated into finite sets,
when ?k, = k derivation strategies are used, and regular or context-free sets, respectively, are obtained for ?k, * and terminal derivation strategies. In both cases, regular or context-free grammars, the regular sets are translated into non-context-free
languages. Moreover, any language accepted by a Turing machine may be written as a translation of a regular set performed
by a generalised stream X-machine with underlying distributed grammars based on context-free rules, under = k derivation strategy. On the other hand the languages generated by some classes of cooperating distributed grammar systems
may be obtained as images of regular sets through some X-machines with underlying distributed grammars. Other relations of
the families of languages computed by generalised stream X-machines with the families of languages generated by cooperating
distributed grammar systems are established. At the end, an example dealing with the specification of a scanner system illustrates
the use of the introduced mechanism as a formal specification model.
Received September 1999 / Accepted in revised form October 2000 |
| |
Keywords: | : Computational models Cooperating distributed grammar systems Formal grammars Generalised stream X-machines Turing machines |
本文献已被 SpringerLink 等数据库收录! |
|