GATE 2023 CS – Question 39
Consider the context-free grammar G below: S → aSb | X; X → aX | Xb | a | b, where S and X are non-terminals, and a and b are terminal symbols. The starting non-terminal is S. Which one of the following statements is CORRECT?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (B) The language generated by G is $a^*(a+b)b^*$
Explanation
$G$: $S\to aSb\mid X$, $X\to aX\mid Xb\mid a\mid b$.
**What $X$ generates.** $X$ can start from `a` or `b` (one symbol), and then add `a`'s on the left (via $X\to aX$) and `b`'s on the right (via $X\to Xb$). So $L(X)=a^*(a+b)b^*$.
**What $S$ generates.** $S\to aSb$ wraps the result with an `a` on the left and a `b` on the right, $n$ times, then uses $X$: $a^nXb^n$. Since $X$ already allows any number of `a`'s on the left and `b`'s on the right, $L(S)=a^*(a+b)b^*$ as well.
So $L(G)=a^*(a+b)b^*$, which is regular: option (B).