GATE CS 2017 Set 1 Q.10 (CS Q.10): Context-Free Grammars, Pushdown Automata and CFLs

Consider the following context-free grammar over the alphabet $\Sigma = \{a, b, c\}$ with $S$ as the start symbol:

S \to abScT \mid abcT

T \to bT \mid b

Which one of the following represents the language generated by the above grammar?

$\{(ab)^n (cb)^n \mid n \ge 1\}$

$\{(ab)^n c b^{m_1} c b^{m_2} \dots c b^{m_n} \mid n, m_1, m_2, \dots, m_n \ge 1\}$

$\{(ab)^n (cb^m)^n \mid m, n \ge 1\}$

$\{(ab)^n (cb^n)^m \mid m, n \ge 1\}$

Official answer and solution

Official answer: B
From: Official GATE 2017 answer key

Solution

Derive strings from the start symbol $S$ to find the structural pattern of the generated language.

Consider the production rules for non-terminal $T$ :

T \to bT \mid b

Starting from $T$ , we have:

T \implies b, \quad T \implies bb, \quad T \implies bbb, \quad \dots

Thus, $T$ generates $b^+$ (any non-empty sequence of $b$ 's, i.e., $b^m$ with $m \ge 1$ ).

Now consider the productions for $S$ :

S \to abScT \mid abcT

If we apply the base rule $S \to abcT$ once ( $n = 1$ ), we obtain:

S \implies abcT \implies abcb^{m_1} \quad (m_1 \ge 1)

If we apply the recursive rule $S \to abScT$ once and then the base rule ( $n = 2$ ):

S \implies ab S c T_2 \implies ab (abc T_1) c T_2 = (ab)^2 c T_1 c T_2 \implies (ab)^2 c b^{m_1} c b^{m_2} \quad (m_1, m_2 \ge 1)

Applying the recursive rule $n - 1$ times followed by the base rule yields:

S \implies (ab)^{n-1} S (c T)^{n-1} \implies (ab)^n c T_1 c T_2 \dots c T_n

Each $T_i$ independently derives any string in $b^+$ , so each $m_i \ge 1$ is chosen independently.

Thus, the generated language is:

\{(ab)^n c b^{m_1} c b^{m_2} \dots c b^{m_n} \mid n, m_1, m_2, \dots, m_n \ge 1\}

Notice that Option C requires all exponents of $b$ to be identical ( $m$ ), which is not true since each $T_i$ derives independently. Hence, Option B is correct.

Final answer

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

Source

Paper: GATE 2017 Computer Science and Information Technology (CS) Session 1
Question: 10 of 65, printed as CS Q.10
Section: Computer Science and Information Technology

Report an error in this question

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

Question

Solution

Source