Context Free Grammar Help?

Question

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--> aXb | e
Y--> cYd | e
Then I assume you just add a start a start line like:
S--> 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.

Answer 1

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 --> 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.

Answer 2

In Timbuktu does no longer count number which it is. both do no longer make when you consider that to me. So come to Timbuktu the position there is none of your conventional grammar and a context-loose grammar. Mmmmmmmmk by technique of by technique of!

Answer 3

I don't think that's even possible with a context free grammar....