Consider the context-free grammar G below. Here S is the starting non-terminal…
2023
Consider the context-free grammar G below. Here S is the starting non-terminal symbol, while a and b are terminal symbols.
S→aSb∣T
T→bT∣b
The language generated by G is:
- A.
{ambn:0≤m<n}
- B.
{ambn:0<m<n}
- C.
{ambn:0<m≤n}
- D.
{anbn:n≥0}
Attempted by 28 students.
Show answer & explanation
Correct answer: A
S→aSb∣T
This means:
You can wrap a at the beginning and b at the end repeatedly
Eventually terminate with T=b+
Build the pattern
Let’s apply the rule:
Apply S→aSb n times
Then terminate with T=bm, where m≥1
Each time:
Add one a at front
Add one b at end
So final string becomes:
an bm bn
Which simplifies to: {ambn:0≤m<n}
which is option A.