A context free grammar for \(L=\{w \mid n_0 (w) > n_1 (w)\}\) is given by :

Grammar under review:

S → 0 | 0S | 1SS | S1S | SS1

Correctness (every string derived has strictly more 0s than 1s):

• Base case: S → 0 produces a string with one more 0 than 1 (difference = 1).

• If S derives a string x with difference d(x) = #0(x) − #1(x) ≥ 1, then 0S derives 0x with difference d(0x) = d(x) + 1 ≥ 2, so still positive.

• For the productions placing a single 1 and concatenating two S-substrings, say 1SS produces 1xy when the two S-instances yield x and y. Then d(1xy) = d(x) + d(y) − 1. Since each of d(x), d(y) ≥ 1 by the invariant, d(1xy) ≥ 1. The same argument applies to S1S and SS1.

Thus every string generated by this grammar has #0 > #1.

Completeness (every string with #0 > #1 can be derived):

1. Proof by induction on m = #0 − #1 (m ≥ 1).

2. Base m = 1: If the string contains only zeros then repeated use of 0S and finally S → 0 derives it. If the string contains at least one 1, there are at least two zeros in total somewhere; split the suffix of the first 1 into two parts so both parts have nonnegative difference and at least one of them positive, then apply one of the productions that inserts a 1 between two S components. (A short constructive split exists because the total difference is positive.)

3. Inductive step: assume every string with difference < m is derivable. Take a string w with difference m. If w begins with 0, use production 0S and apply the induction hypothesis to the remainder (which has difference m−1). If w begins with 1, write w = 1uv or w = u1v or w = uv1 so that u and v are substrings obtained by splitting the remainder into two parts with positive differences (such a split exists because the total difference m ≥ 1). Then use the corresponding production 1SS, S1S or SS1, and apply the induction hypothesis to derive u and v from S (their differences are smaller and at least 1).

Therefore the grammar generates exactly the language { w | #0(w) > #1(w) }.

Example derivation (sketch): derive "00100" (zeros = 4, ones = 1, difference = 3). Start with 0S → 0 0S → 00 (use production to insert a 1 in middle) 00(1SS) ... then derive remaining parts by repeated 0S and final S → 0. The invariant and the inductive construction ensure a full derivation exists.