# Demonstrating that for every monotonic grammar there is an equivalent context-sensitive grammar

I'm trying to understand the equivalence in expressive power of formal grammars whose rules take the form:

$$\alpha \rightarrow \beta$$ where $|\alpha| \leq |\beta|$ (called a monotonic grammar), and grammars whose rules take the form:

$$\alpha B \gamma \rightarrow \alpha C \gamma$$

where $\alpha$ and $\gamma$ are strings of terminals & non-terminals or possibly empty, and $B$ and $C$ are single non-terminals. I understand that grammars of the second kind are already, by definition, grammars of the first kind, but I'd like to understand how to derive a grammar of the second kind, given one of the first kind (a monotonic grammar). Can anyone suggest a good reference for this? Many thanks in advance.

First replace ever terminal $$a$$ with a non-terminal $$X_a$$ and add a production $$X_a \to a$$, because context sensitive grammars only work on non-terminals. Then, for every production $$A_1\dots A_n \to B_1\dots B_n$$ create new non-terminal $$D$$ and replace the production with a sequence of productions \begin{align} A_1A_2\dots A_n &\to DA_2\dots A_n \\ DA_2A_3\dots A_n &\to DB_2 A_3 \dots A_n \\DB_2A_3A_4\dots A_n &\to DB_2 B_3A_4 \dots A_n \\ &\vdots \\ DB_2\dots B_{n-1}A_n &\to DB_2\dots B_{n-1}B_n \\ DB_2 \dots B_n &\to B_1B_2 \dots B_n \end{align}which are all context sensitive. Also, replace every production $$A_1 \dots A_n \to B_1 \dots B_m$$ where $$n < m$$ with \begin{align} A_1\dots A_n &\to B_1\dots B_{n-1}C \\ C &\to B_nB_{n+1} \dots B_m\end{align}where the first production can be made context sensitive as previously shown and the second one is context free. Of course, this construction may introduce problems (if $$B_1A_2 \to \dots$$ is already in the grammar, for instance). This is easily solved by adding new non-terminals.