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
