# Context-sensitive grammars without permutation rules

Permutation rules are called those which are of the form $AB\Rightarrow^*BA$1. It is also proven that permutation rules expand context-free grammars and allow them produce non-context-free languages.

My question is: are any examples of context-sensitive grammars, which doesn't contain any permutation rules but still able to produce non-context-free languages?

1) Book, R.V. International Journal of Computer and Information Sciences (1973) 2: 129. doi:10.1007/BF00976059. More generally permutation rules have form of $Y_1 \dots Y_m\rightarrow Y_{\pi_1}\dots Y_{\pi_m}$, where $\pi$ is some permutation of $\{1\dots m\}$.

• Welcome to CS.SE! Interesting question! What have you tried? Have you tried constructing such an example yourself? Have you tried working through a few examples of simple context-sensitive grammars that don't have any permutation rules to see what kind of language they generate, and whether it is context-free? The site tends to work better if you try to solve your own question yourself before asking, and show us in the question what attempts or progress you've already made. – D.W. Nov 4 '16 at 21:43
• How about this example, It does not seem to have any permutation rules as far as I can tell. – aelguindy Nov 4 '16 at 23:11
• @aelguindy Thank you for you commentary. This grammar example in wikipedia is composed by my self (you can see edit history of article), as previous one was incorrect. Essentially it has permutation rule $CB\Rightarrow* BC$, which is expanded into four rules – Andrey Lebedev Nov 4 '16 at 23:23
• @Andremoniy oh sorry, I did miss the star on the arrow in your question. (Back to thinking :)) – aelguindy Nov 4 '16 at 23:26
• I suspect that permutations may ne needed for the whole class CSL. You may want to look at mildly context-sensitive formalisms and the proofs that they model subsets of CSL; if a simulation does not introduce permutations, you have found a solution. – Raphael Jan 29 '17 at 16:56

You have the Koruda normal form in mind. It is indeed often useful, in particular in simulation LBAs.

However, many definitions of CSGs (including Chomsky's) are different; they require rules to have the form

$\qquad \alpha A \beta \to \alpha \gamma \beta$.

You can see how this precludes "permutation rules".

Obtain a concrete grammar by applying the simulation you find in a proof that KNF is equivalent to the classical definition.

• Upon reading the comments on the question, I'm not sure this is immediately helpful. Permutations can be implemented by a series of rules, I guess -- otherwise the proof I refer to wouldn't work. – Raphael Jan 29 '17 at 16:49
• that's true, that's what I wanted to write: each permutation rule indeed can be expanded into 4 "canonical" rules of given form $\alpha A\beta\rightarrow\alpha\gamma\beta$, so question still reminds. – Andrey Lebedev Jan 29 '17 at 17:49

Perhaps this might not directly answer your question, but I know of a very innocent grammatical concept that moves context-free grammars outside the context-free language area.

Start with a context-free grammar, and apply productions in the usual way, except that always two adjacent non-terminals are rewritten. This mode of rewriting grammars was proposed by Kleijn and Rozenberg. The proof that such languages are outside context-free was given in "Concerning two-adjacent context-free languages" by Dahlhaus and Gaifman (1985, Open Archive at Elsevier Theoretical Computer Science). Their paper is a little technical and studies the connection to E0L-languages (that have parallel derivation steps), but I found a concrete example.

They propose the following grammar for $\{b^{4k}\mid k\ge 1\}$ when used in 2-adjacent mode (Lemma 2.3).

$S\to bABb$, $S\to bb$, $A\to bA$, $B\to bB$, $A\to b$, $B\to b$

So, note that as context-sensitive (or better non-contracting/monotonic grammar) we would translate this as all pairs of productions, like $SA \to bABb\,bA$, but strictly speaking these rules are not permutation rules.

• I guess we would restrict the grammars so that only one non-terminal may be replaced, i.e. context has to be preserved. – Raphael Jan 29 '17 at 16:39
• Regarding your answer, a context-sensitive grammar is missing. – Raphael Jan 29 '17 at 16:39