文章基本信息

标题：Grammars Based on the Shuffle Operation
本地全文：下载
作者：Gheorghe Paun ; Grzegorz Rozenberg ; Arto Salomaa 等
期刊名称：Journal of Universal Computer Science
印刷版ISSN：0948-6968
出版年度：1995
卷号：1
期号：1
页码：67-82
出版社：Graz University of Technology and Know-Center
摘要：We consider generative mechanisms producing languages by starting from a finite set of words and shuffling the current words with words in given sets, depending on certain conditions. Namely, regular and finite sets are given for controlling the shuffling: strings are shuffled only to strings in associated sets. Six classes of such grammars are considered, with the shuffling being done on a left most position, on a prefix, arbitrarily, globally, in parallel, or using a maximal selector. Most of the corresponding six families of languages, obtained for finite, respectively for regular selection, are found to be incomparable. The relations of these families with Chomsky language families are briefly investigated.