GATE CS 2023 Q.39: Context-Free Grammars, Pushdown Automata and CFLs

Consider the context-free grammar $G$ below

\begin{aligned} S &\rightarrow aSb \mid X \\ X &\rightarrow 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?

The language generated by $G$ is $(a + b)^*$

The language generated by $G$ is $a^* (a + b)b^*$

The language generated by $G$ is $a^* b^* (a + b)$

The language generated by $G$ is not a regular language

Official answer and solution

Solution

Analyze the strings generated by non-terminal $X$ and their embedding into $S$ .

Non-terminal $X$ has productions:
$X \rightarrow aX \mid Xb \mid a \mid b$
This grammar generates any string consisting of one or more characters from $\{a, b\}$ where all $a$ 's appear before all $b$ 's, i.e., $L(X) = a^* (a + b) b^* = a^+ b^* \cup a^* b^+$ .
Non-terminal $S$ has productions:
$S \rightarrow aSb \mid X$
Applying $S \rightarrow aSb$ $k$ times ( $k \ge 0$ ) wraps the string generated by $X$ with $k$ leading $a$ 's and $k$ trailing $b$ 's:
$a^k X b^k = a^k [a^* (a + b) b^*] b^k = a^* (a + b) b^*$
Because absorbing additional $a$ 's on the left and $b$ 's on the right of $a^* (a + b) b^*$ yields precisely the same set $a^* (a + b) b^*$ , the language generated is simply $L(G) = a^* (a + b) b^*$ .
Since $a^* (a + b) b^*$ is a regular expression, the language is regular.

Final answer

Option (B)

Common trap

Concluding the language is non-regular due to the $S \rightarrow aSb$ production without realizing $X$ already generates all unbalanced combinations.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.