ON A HIERARCHY OF PERMUTATION LANGUAGES

The family of context-free grammars and languages are frequently used. Unfortunately several important languages are not context-free. In this paper a possible family of extensions is investigated. In our derivations branch-interchanging steps are allowed: language families obtained by context-free and permutation rules are analysed. In permutation rules both sides of the rule contain the same symbols (with the same multiplicities). The simplest permutation rules are of the form AB → BA. Various families of permutation languages are defined based on the length of non-context-free productions. Only semi-linear languages can be generated in this way, therefore these language families are between the context-free and context-sensitive families. Interchange lemmas are proven for various families. It is shown that the generative power is increasing by allowing permutation rules with length three instead of only two. Closure properties and other properties are also detailed.