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

Question

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.

Answer 1

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.