If G=({ S}, {0,1}, { S → OS1, S → ^}, S) then find L(G), the language generated by G.

Solution: Since S → ^ is a production, S ⇒ ^.  This implies that ^ ∈ L(G).

Now, for all n ≥ 1, we can write the following:

S ⇒ 0S1 ⇒ 00S11 …  ⇒ 0ⁿS1ⁿ ⇒ 0ⁿ1ⁿ.

Therefore, 0ⁿ1ⁿ  ∈ L(G). 

In the above derivation, at every step, S → 0S1 is applied, except in the last step where S → ^ is applied.  

Therefore, {0ⁿ1ⁿ  n ≥ 0} ⊊ L(G).

Now suppose w ∈ L(G).  So we should start the derivation of w with S.

If we are applying S → ^ first, then we will get w = ^.

Otherwise, the first production that we need to apply is S → 0S1. 

However, at any stage we can apply S → ^ to obtain the terminating string.  Therefore w can be derived in the following form.

S ⇒ 0ⁿS1ⁿ � 0ⁿ1ⁿ, for some n ≥ 1, That is L(G) ⊊ {0ⁿ1ⁿ | n ≥ 0}.

Hence L(G) = {0ⁿ1ⁿ   n ≥ 0}.