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.
2006-10-23
17:58:11
·
3 answers
·
asked by
mdigitale
7
in
Mathematics