An example of a context-sensitive grammar for a given language

Consider this language: $$L = \{a^nb^ma^nb^m \mid n,m \ge 1\}$$. Can we give for this language a context-sensitive grammar?

• Wikipedia contains a noncontracting grammar, which can easily be converted to a context-sensitive grammar. – Yuval Filmus Oct 21 '19 at 20:13

$$\begin{array}{lcl} &S &\to &abab\\ &ba &\to &bbBa\\ &Ba &\to &aB\\ &Bb &\to &bb\\ &ba &\to &bAaa\\ &bA &\to &Ab\\ &aA &\to &aa\\ \end{array}$$

There is some theory to help you make sense of this solution.

Let us first consider a simpler language that manifests the same difficulty: $$L = \{a^nb^ma^n ∣ n,m \ge 1\}$$. Imagine it as a sea of $$b$$ between the shores of $$a$$, if you please.

We would like to grow the shores so that they are always the same size. One immediate way is to have a collection of rules like $$a + b^m + a \to aa + b^m + aa$$. But we see it will not serve our needs, as, our collection being finite (grammars are required to have a finite set of rules), there is always some choice of $$m$$ that is not accomodated. So evidently there is a trick.

The trick is to introduce a non-terminal "ship" that will sail across the sea and deliver the information from one shore to the other. When the left shore grows, it will send a ship to the right shore, and when the right shore receives a ship, it will also grow, thus maintaining the required equilibrium. How can we sail a ship? $$Ba \to aB$$ is one way to move it one unit of sea rightwards. What remains to be put in place is a shipyard $$ba \to bbBa$$ and a port $$Bb \to bb$$.

Here is what we get:

$$\begin{array}{lcl} &S &\to &bab\\ &ba &\to &bbBa\\ &Ba &\to &aB\\ &Bb &\to &bb\\ \end{array}$$

I am sure you can see how to extend this to your original language: you will need the sea people to also send some sort of messenger golems $$A$$ across the land to the sea on the other side of $$b$$.

Happy adventures in fantasy grammar land!