Languages Generated by Context-Free Grammars Extended by Type AB → BA Rules
Benedek Nagy · Journal of automata, languages and combinatorics · 2009
Derivations using branch-interchanging and language family obtained by context-free and interchange ($AB \to BA$) rules are analyzed. This language family is between the context-free and context-sensitive families. Closure properties and other properties are detailed. Only semi-linear languages can be generated in this way. Relation to partial commutations is shown.