[Solved]: Demonstrating that for every monotonic grammar there is an equivalent context-sensitive grammar

Problem Detail: 

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.

Asked By : BlueBomber

Answered By : Karolis Juodelė

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/7734

 Ask a Question

 Download Related Notes/Documents