The following CFG S → aB | bA A → a | aS | bAA B → b | bS | aBBgenerates…

Concept: the language of a context-free grammar is identified by finding a quantity that every production preserves and then arguing by induction on the number of derivation steps. Over a two-letter alphabet the natural quantity is the difference d(w) = (number of a’s in w) − (number of b’s in w), because each production changes it by a fixed amount that can be read straight off the right-hand side.

Application: give each non-terminal a claimed value of d — d = +1 for A, d = −1 for B, and d = 0 for S — and then check every production for consistency with that assignment by adding up the contributions of the symbols on its right-hand side.

1. A → a contributes one a and no b, so d = +1.

2. A → aS contributes +1 from the leading a and 0 from S, so d = +1.

3. A → bAA contributes −1 from the leading b and +1 from each of the two As, so d = −1 + 1 + 1 = +1.

4. B → b contributes one b and no a, so d = −1.

5. B → bS contributes −1 from the leading b and 0 from S, so d = −1.

6. B → aBB contributes +1 from the leading a and −1 from each of the two Bs, so d = +1 − 1 − 1 = −1.

7. S → aB contributes +1 from the leading a and −1 from B, so d = 0.

8. S → bA contributes −1 from the leading b and +1 from A, so d = 0.

Every production respects the assignment, so induction on the number of derivation steps gives d(w) = 0 for every terminal string w derivable from S: such a string always carries as many a’s as b’s.

The converse holds as well, which is what makes the description exact rather than merely necessary. A non-empty string with d = 0 either begins with a and leaves a remainder of d = −1, which B supplies, or begins with b and leaves a remainder of d = +1, which A supplies. A string with d = −1 beginning with b leaves a remainder of d = 0, matching B → bS; one beginning with a leaves a remainder of d = −2, and since the running difference moves one step at a time that remainder can always be cut into two consecutive pieces of d = −1 each, matching B → aBB. The reasoning for A is the mirror image, and only the empty string is left out, because no production deletes a non-terminal.

Cross-check by deriving concrete strings:

• S ⇒ aB ⇒ ab — one a and one b.

• S ⇒ bA ⇒ ba — one a and one b.

• S ⇒ aB ⇒ aaBB ⇒ aabB ⇒ aabb — two a’s and two b’s.

• S ⇒ aB ⇒ abS ⇒ abaB ⇒ abab — two a’s and two b’s.

Contrast with the other descriptions on offer: ab carries an odd count of each letter while aabb carries an even count of each, and both are derivable, so no single parity condition covers the whole language; and because d(w) = 0 always holds, a string whose two counts differ can never be derived. The language is therefore exactly the set of non-empty strings over {a, b} that contain equally many a’s and b’s.