Consider the context-free grammar G below. Here S is the starting non-terminal…
2025
Consider the context-free grammar G below. Here S is the starting non-terminal symbol, while a and b are terminal symbols.

The language generated by G is:
Attempted by 31 students.
Show answer & explanation
First, analyze the non-terminal T. The production rules are T → bT and T → b. This generates strings consisting of one or more 'b's. So, L(T) = { b^n | n ≥ 1 }.
Next, analyze the non-terminal S. The rules are S → aSb and S → T. The rule S → aSb allows us to add an 'a' at the beginning and a 'b' at the end of any string generated by S. If we apply this rule k times, we get a structure like a^k S b^k.
Finally, to terminate the recursion, we must use S → T. This replaces S with a string from L(T). Combining these, any string generated by S has the form a^k w b^k, where w ∈ L(T). Since w = b^n for some n ≥ 1, the total string is a^k b^n b^k = a^k b^{n+k}.
Let m = k be the number of 'a's and the total exponent of 'b' be N = n+k. Since n ≥ 1, we have N > k, which means the number of 'b's is strictly greater than the number of 'a's. Also, k can be 0 (if we go directly to T), so the number of 'a's can be 0. Therefore, the language is { am bn | 0 ≤ m < n }.