Context Free Grammar Help?

Hello. I find CFGs interesting, however I am having an extremely difficult time visualizing how to construct them. For example, if I am told (a^m)(b^n)(c^p)(d^q) such that m + n = p + q is the definition for valid strings in the language, how can I convert that to the CFG syntax? I can see from the m+n = p+q condition that the resulting string is going to be something that can be divided equally (ie. even) but I can't see how that would help me. Also, it is possible to choose "nice" strings that are in this language, say aaabbbcccddd because then I can break the string into two rules like:


X--%26gt; aXb | e


Y--%26gt; cYd | e


Then I assume you just add a start a start line like:


S--%26gt; X | Y | e





This is the solution I get from the speically chosen string. I doubt that my CFG above is correct for any string in the language. Can anyone provide some guidance and tips? Thank You so much.

Context Free Grammar Help?
Do a Y!A search for "context free grammar" to see similar problems.





Here's an example:





aaabbbbbccdddddd





Group it:





aaa [ bbb ( bbcc ) ddd ] ddd





Use one rule T1 to generate the middle part: a number of b's followed by same number of c's. Using T1, make another rule T2 to add an equal number of b's and d's at the ends:





T2 --%26gt; T1 | b T1 d





Make a rule S1 to add equal number of a's and d's.





This works when there are more b's than c's. Do something similar when there are more c's than b's to get S2.





Finally, S is S1 or S2.
Reply:I don't think that's even possible with a context free grammar....