Context Free Language Question?

Question

Hello, I'm new to context free languages and having trouble converting from a mathematical description of a language into the CFG syntax. For example, if I'm asked to find (a^n)(b^n) for n greater or equal to zero, that is a language that has the same number as a's as b's that begins with "a", i know that I can write the context language as:
S-->aSb | e

How do I handle a situation where I have something like:
(a^m)(c^p)(d^q) such that m = p + q.

Anyone have an idea??
Thanks

Thanks for your response. I'm always amazed how simple little things can bring the full picture to a whole new light. I'm not quite sure if this is all there is to it? For example, what would happen if m was chosen to be 1...therefore p OR q must be 1.

So valid strings would be ac or ad
And the rule would be quite simiple
S-->ac | ad

I don't know why these things are so difficult for me to visualize. I feel like I should be able to write a general CFG that encompasses the m = p + q condition not dependant upon the actual values chosen? Am I off base here?

Answer 1

Here's an example and a hint:

aaaaaaaacccddddd

= aaaaa ( aaaccc ) ddddd

You can easily generate the middle part with a rule. After that generate the outer part with another rule.

MORE DETAILS

One rule T must generate a number of a's followed by an equal number of 'c's : a^p c^p. The number can be 0, so includes the empty string, e.

Using T make another (main) rule S to generate a number of a's followed by T followed by an equal number of d's: a^q T d^q. The number can be 0, so includes the result of generating T.

ac is generated: T generates one of each: ac, then S generates 0 of extra a and d.

ad is generated: T generates 0 of a and c to get e, then S generates 1 of extra a and d.

Better to represent the language as

a^(p+q) c^p d^q, or as

a^q a^p c^p d^q

to see the required pattern, rather than thinking of m = p+q as a condition to be satisifed by the rules.

T --> e | a T c
S --> T | a T d