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

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

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!

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.