Grammars Based on the Shuffle Operation

Gheorghe Paun (Institute of Mathematics of the Romanian Academy of Sciences, Romania)

Grzegorz Rozenberg (University of Leiden, Department of Computer Science, The Netherlands)

Arto Salomaa (Academy of Finland and University of Turku, Department of Mathematics, Finland)

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: Chomsky grammars, L Systems, Shuffle operation

Categories: F.4.2, F.4.3