How to write this CFG?

Question

the question is to construct a CFG which generates language

my solution is: S -> aSb | aS | bS | a | b, however, this grammar can also generate strings like aabb, so how to do it?

Thanks for help.

Answer 1

So you want a string of a's then a string of b's, with an unequal number of a's and b's. First, let's ignore the equality condition. Then:

S -> aSb | 0

will generate all strings that start with a's and then b's. This rule guarantees an equal number of a's and b's, or the empty string. Now what we want is either more a's, or more b's, but not both. Because if we wanted one more a AND one more b, we'd just apply S again. So we add two new rules:

A -> aA 
B -> bB

and update S to be:

S -> aSb | A | B

So now we can add an equal number of a and b, or add more a's, or add more b's, but not both. This guarantees inequality, so we're almost done. If you don't need the empty string, you can just stop here. For the null string, we can't do:

S -> aSb | A | B | 0,

because that can lead to S -> aSb -> a0b -> ab, which violates the condition. We also can't do:

A -> aA | 0,

because that can produce S -> aSb -> aAb -> a0b -> ab. So what do we do? The trick is to force S's later expansions to have at least one a or b, like this:

S -> aSb | aA | bB
A -> aA | 0
B -> bB | 0

and that's your solution.