The GATE Grind

GATE 2023 CS – Question 39

Theory of Computation · Context-Free Grammars and Pushdown Automata · 2 marks · Multiple choice

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?

  1. The language generated by G is $(a+b)^*$
  2. The language generated by G is $a^*(a+b)b^*$
  3. The language generated by G is $a^*b^*(a+b)$
  4. The language generated by G is not a regular language

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

More Context-Free Grammars and Pushdown Automata questions

All Context-Free Grammars and Pushdown Automata questions →