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_1dots A_n to B_1dots B_n$ with a sequence of productions $$begin{align} A_1A_2dots A_n &to B_1A_2dots A_n B_1A_2A_3dots A_n &to B_1B_2 A_3 dots A_n &vdots B_1dots B_{n-1}A_n &to B_1dots 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_1dots A_n &to B_1dots B_{n-1}C C &to B_nB_{n+1} dots B_mend{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
