[Solved]: Constructing an unrestricted grammar for a^n b^m c^n d^m

Problem Detail: 

I've been trying to construct an unrestricted grammar which has the language:

L = {a^n b^m c^n d^m | n>0, m>0}

But I can't seem to figure it out without making the derivations run an unreasonably long amount of time. Can anyone help me devise an elegant way to create this grammar?

Edit: In order to clarify, I was trying to find an Unrestricted Grammar that would run in O(n^2) time or better. As it stood, all of my solutions were exponential, which made parsing very long strings prohibitively costly.

Asked By : weskpga

Answered By : Yuval Filmus

How about the following: $$ \begin{align*} &S \to XY \\ &X \to aXC | aC \\ &Y \to BYd | Bd \\ &CB \to BC \\ &aB \to ab \\ &bB \to bb \\ &Cd \to cd \\ &Cc \to cc \\ \end{align*} $$ In this grammar you need to apply $O(nm)$ rules to get $a^nb^mc^nd^m$.

Best Answer from StackOverflow

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