The GATE Grind

GATE 2017 CS – Question 20

Theory of Computation · Context-Free Grammars and Pushdown Automata · 1 mark · Multiple choice

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

$S \rightarrow abScT \mid abcT$

$T \rightarrow bT \mid b$

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

  1. $\{(ab)^n (cb)^n \mid n \geq 1\}$
  2. $\{(ab)^n cb^{m_1} cb^{m_2} \ldots cb^{m_n} \mid n, m_1, m_2, \ldots, m_n \geq 1\}$
  3. $\{(ab)^n (cb^m)^n \mid m, n \geq 1\}$
  4. $\{(ab)^n (cb^n)^m \mid m, n \geq 1\}$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) $\{(ab)^n cb^{m_1} cb^{m_2} \ldots cb^{m_n} \mid n, m_1, m_2, \ldots, m_n \geq 1\}$

Explanation

Each use of $S \rightarrow abScT$ adds "ab" at the front and "$cT$" at the back, and the last step uses $abcT$. After $n$ steps the string is $(ab)^n$ followed by $n$ blocks of the form $c\,b^{m}$, where each $T$ gives one or more $b$'s independently. So the language is $(ab)^n c b^{m_1} c b^{m_2} \cdots c b^{m_n}$ with all $m_i \geq 1$.