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

X generates a*(a+b)b*. S wraps X as a^n X b^n, which still gives strings of the form a*(a+b)b*. So L = a*(a+b)b*, which is regular.