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

Question

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

Answer 1

Your request is easily served!

$$\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!