Does anybody have experience with this? Specifically, I would really like to know if there is some sort of process that can be followed to create a CFG when given a language. I can do it intuitively for simple languages (equal number of a's and b's, simple palindromes, etc.) but I really don't know of a good method to do this for more difficult cases.
For example, how would I go about creating a CFG for the following language:
Intuitively, I know that this means that there can't be an equal number of a's, b's, and c's. There can be:
- equal number of a's and b's, but different number of c's
- equal number of a's and c's, but different number of b's
- equal number of b's and c's, but different number of a's
- different number of a's, b's, and c's
Does this mean that I need 4 non-terminals? What is the best way to approach this sort of problem?
For example, how would I go about creating a CFG for the following language:
Code:
a^i b^j c^k : i,j,k >= 0 and (i != j OR j != k)Intuitively, I know that this means that there can't be an equal number of a's, b's, and c's. There can be:
- equal number of a's and b's, but different number of c's
- equal number of a's and c's, but different number of b's
- equal number of b's and c's, but different number of a's
- different number of a's, b's, and c's
Does this mean that I need 4 non-terminals? What is the best way to approach this sort of problem?
Facebook
Twitter