GATE CS 2023 (Forenoon) — Question 39

Theory of Computation (TOC)Context-Free Grammars & Push-Down AutomataMCQ2 marks · −2/3 if wrongMedium

Consider the context-free grammar \( G \) below: \( S \rightarrow aSb \mid X \) \( X \rightarrow aX \mid Xb \mid a \mid 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. A
    The language generated by \( G \) is \( (a + b)^* \)
  2. B
    The language generated by \( G \) is \( a^*(a + b)b^* \)
  3. C
    The language generated by \( G \) is \( a^*b^*(a + b) \)
  4. D
    The language generated by \( G \) is not a regular language
Practise the full 2023-FN paper
Challenge a friend: WhatsApp Telegram
From RENYXERAPractise this subject in the exam simulatorTimed, GATE-style tests with analytics that find your weak topics.
Practise more on Context-Free Grammars & Push-Down AutomataTimed, in the real exam interface · free to start

A GATE question every morning

One real past-paper question every morning for your branch, answer hidden until you tap. Free on Telegram.

Join
Stuck? Ask in the student group