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.


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.