Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 3 down vote accepted

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, replace every production $A_1\dots A_n \to B_1\dots B_n$ with a sequence of productions $$\begin{align} A_1A_2\dots A_n &\to B_1A_2\dots A_n \\ B_1A_2A_3\dots A_n &\to B_1B_2 A_3 \dots A_n \\ &\vdots \\ B_1\dots B_{n-1}A_n &\to B_1\dots B_{n-1}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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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