In the context-free grammar below, S is the start symbol, a and b are…
2006
In the context-free grammar below, S is the start symbol, a and b are terminals, and ϵ denotes the empty string.
S → aSAb | ϵ
A → bA | ϵ
The grammar generates the language
- A.
((a + b)* b)*
- B.
{ambn | m ≤ n}
- C.
{ambn | m = n}
- D.
a* b*
Attempted by 12 students.
Show answer & explanation
Correct answer: B
The grammar has productions S → aSAb | ϵ and A → bA | ϵ. Starting from S, each application of S → aSAb adds one 'a' and one 'b', but A can generate any number of b's including zero. This means for every a, there is at least one corresponding b or more, leading to strings where the number of a's (m) is less than or equal to the number of b's (n). The language generated is {am bn | m ≤ n}, matching option B. Option C would require equal counts, which is not enforced here.