The following Context-Free Grammar (CFG) : S → aB | bA A → a | aS | bAA B → b…

Answer: the grammar generates all strings with equal numbers of a's and b's.

Reason (invariant proof):

• Invariant for A: any string derived from A has one more a than b (a = b + 1).

• Why A satisfies this: A → a gives (a=1,b=0); A → aS keeps the +1 difference because S produces equal numbers; A → bAA: if each A_i satisfies a_i = b_i + 1, then total a = (b1+1)+(b2+1) = (b1+b2)+2 and total b = 1 + b1 + b2, so a = b + 1.

• Invariant for B: any string derived from B has one more b than a (b = a + 1).

• Why B satisfies this: B → b gives (b=1,a=0); B → bS keeps the +1 difference because S produces equal numbers; B → aBB: if each B_i satisfies b_i = a_i + 1, then total b = (a1+1)+(a2+1) = (a1+a2)+2 and total a = 1 + a1 + a2, so b = a + 1.

• Conclusion for S: S → aB gives one leading a plus a string from B; because B has one more b than a, the overall counts become equal. Similarly S → bA gives one leading b plus a string from A, and A has one more a than b, so totals match. Hence every string derived from S has equal numbers of a's and b's.

Examples:

• S → aB → a b gives "ab" (1 a, 1 b).

• S → aB → a aBB → a a b b gives "aabb" (2 a's, 2 b's).