Grammars Based on the Shuffle Operation

Gheorghe Paun; Grzegorz Rozenberg; Arto Salomaa

doi:10.3217/jucs-001-01-0067

JUCS - Journal of Universal Computer Science 1(1): 67-82, doi: 10.3217/jucs-001-01-0067

Grammars Based on the Shuffle Operation

Gheorghe Paun^‡, Grzegorz Rozenberg^§, Arto Salomaa^|

‡ Institute of Mathematics of the Romanian Academy, Bucharest, Romania§ University of Leiden, Department of Computer Science, Netherlands| Academy of Finland and University of Turku, Department of Mathematics, Turku, Finland

Corresponding author: Gheorghe Paun

This article is freely available under the J.UCS Open Content License.

Citation: Paun G, Rozenberg G, Salomaa A (1995) Grammars Based on the Shuffle Operation. JUCS - Journal of Universal Computer Science 1(1): 67-82. https://doi.org/10.3217/jucs-001-01-0067

Abstract

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.

Keywords

Shuffle operation, Chomsky grammars, L Systems