GATE CSE 2023 Q39: Language of S → aSb | X, X → aX | Xb | a | b

Consider the context-free grammar $G$ below

$\begin{aligned} S &\to aSb \mid X \\ X &\to aX \mid Xb \mid a \mid b, \end{aligned}$

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?

Try it: multiple choice: exactly one correct option

Wrong answer costs 2/3 mark in GATE.

Show answer and explanation

Answer: B (official GATE 2023 final answer key)

Concept used: Find the language of the inner non-terminal first, then see what the outer rule adds.

First step: Show that $X$ generates exactly $a^*(a + b)b^*$ , then check what wrapping it in $a^n \ldots b^n$ does.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

Source: official GATE 2023 CS question paper and final answer key, organised by IIT Kanpur. Question paper · Answer key