Creating context free grammars for languages

Question

I'm taking a class on Finite Automata. I'm preparing for a midterm and am having trouble creating Grammars for specific languages. While I find the simple ones very intuitive, when they become more complex, I don't seem to know where to start. For example:

L = { w E { a,b,c}* : nb(w) != na(w) + nc(w) }

The answer is:

S→S1 | S2
S1→bS3 | S3b | S3bS3
S3→S0 | S1
S2→XS4 | S4X | S4XS4
S4→S | S2
S0→bS0XS0 | XS0bS0 | e
X→a | c

If anyone could give me a little guidance on the thought process involved, it would be greatly appreciated.

Answer 1

The language you listed is unclear. I'm assuming w E {a,b,c}* means w ε {a,b,c}* and nb(w) != na(w) + nc(w) means that all strings in the language have a number of b's not equal to the sum of the number of a's and the number of c's.

If this is the case, you have to think about the characteristics of all the strings that will be in the language, and all of the characteristics that will exclude a string from being in this language.

This language accepts strings where the number of b's =/= the number of a's + number of c's. We can reformulate this language to be one that accepts strings that:

number a's + number c's > number of b's OR number a's + number c's < number of b's

This explains the first S --> S1 | S2

S1 ensures that there is at least 1 b (S3), and then forces either an equal amount of b's as a's and c's (S0) or more b's than a's and c's (S1). The net result of the S1 rule is a string with more b's than a's and c's.

S2 ensures that there is more a's and/or c's than b's. It does this by forcing an a or c (X), then allowing an equal amount of a's/c's (S0) or more a's/c's than b's (S2 again).

This is specific to your example, but you can kind of see how the thought process that goes into creating this grammar:

1. Formulate the language as concrete cases (a's/c's > or < b's)
2. For each of the cases, start by making sure the case will hold (force # b's > than a's/c's by forcing at least one b) then expanding the string to include all possibilities of equal a's/c's and b's, or less a's/c's than b's.
3. Symmetrically handle the other case.

The issue is that you need to make sure that every string in the language is generated, and all strings not in the language are not generated. (re-read this until it's implication sinks in)