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

I'm very rusty with CFGs, but thought I'd try to refresh my memory by helping you on this. I might have something, but I've forgotten how to properly validate a CFG, so you might have to check my work. Also, I don't normally spell out the answer completely, but it appears to me you've actually thought about this for a while, which is good.

The way I thought about it is, if you add either 'a' or 'b', you must add either 'c' or 'd' to the string. Furthermore, there is the constraint that all a's must come before all b's, all b's before c's, and all c's before d's.

Since the symmetry is down the middle (a's and b's on one side, c's and d's on the other), I decided to work with a grammar that expanded from the middle, similar to what you have above.

Once I decided on this form, I realized that you'll basically be adding different pairs of letters to generate your string, but the above constraints dictate when the productions change (I'll explain below).

So I started with a production
S --> A
A --> aAd | e

This gives os all strings (a^x)(d^x), all valid strings (n = p = 0).

You might initially think that we could have
A --> aAd | aAc | bAd | bAc | e
to cover the other strings like ac, bd, and bc, but if you think about it a bit more, this gives you broken strings like abaacdcc.

So what happens when we insert either b or c (by insert, I mean insert into the center of the string)? If we insert b, we can no longer insert a, and we must insert a c or d. If we insert c, we can no longer insert d, and we must insert a or b. If we insert both b and c, we can no longer insert a or d. This led me to new productions

A --> aAd | aBc | bCd | bDc | e

Using a similar train of thought for productions B, C, and D, you get

B --> aBc | bDc | e
C --> bCd | bDc | e
D --> bDc | e

Each of these productions, I believe, ensures that we always have to add either a or b whenever we add c or d, and they uphold the order constraint of the strings.

One other thing: the above grammar isn't simplified, so you might want to clean it up a bit, if you've determined that it looks okay.

If you have any questions on this, feel free to email. I don't profess to be very good at these things, but I'll try to help.