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:

  1. A.

    {ambn:0≤m<n}

  2. B.

    {ambn:0<m<n}

  3. C.

    {ambn:0<m≤n}

  4. 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.

Explore the full course: Isro