GateAI
Context-Free Grammars and PDAs

GATE CSE 2017 Set 1 · Q10

MCQ1 markMedium

Time

Consider the following context-free grammar over the alphabet Σ={a,b,c}\Sigma = \{a, b, c\} with SS as the start symbol: S→abScT∣abcTS \rightarrow abScT \mid abcT T→bT∣bT \rightarrow bT \mid b Which one of the following represents the language generated by the above grammar?

Select one answerSingle correct

Pick an option to check

Solution

Step-by-step verified solution

Official answer: B) {(ab)n cbm1cbm2 cbmn n, m1, m2, , mn ≥ 1}

Context-Free Grammars and PDAs

Let us analyze the derivations possible from the grammar:

  1. From the production T→bT∣bT \rightarrow bT \mid b, the non-terminal TT generates any non-empty string of bb's:

    T⇒bm,m≥1T \Rightarrow b^m, \quad m \ge 1
  2. The start symbol SS derives strings recursively:

    • Base case (n=1n = 1):

      S⇒abcT⇒(ab)1cbm1,m1≥1S \Rightarrow abcT \Rightarrow (ab)^1 c b^{m_1}, \quad m_1 \ge 1
    • Recursive step:

      S⇒abScT1⇒ab(abScT2)cT1⇒⋯⇒(ab)ncTncTn−1…cT1S \Rightarrow ab S c T_1 \Rightarrow ab (ab S c T_2) c T_1 \Rightarrow \dots \Rightarrow (ab)^n c T_n c T_{n-1} \dots c T_1
  3. Since each instance of TiT_i can independently derive a sequence of bb's of length mi≥1m_i \ge 1, the language generated is:

    {(ab)ncbm1cbm2…cbmn∣n,m1,m2,…,mn≥1}\{(ab)^n cb^{m_1}cb^{m_2} \dots cb^{m_n} \mid n, m_1, m_2, \dots, m_n \ge 1\}

Notice that the number of bb's following each cc can vary independently (m1,m2,…,mnm_1, m_2, \dots, m_n), but there must be exactly nn occurrences of abab at the beginning matched with nn occurrences of the block cbmic b^{m_i}.

Therefore, (B) is the correct option.

Try the question first, then check your work.

Think the official key or this write-up is wrong?

Report error or challenge

Examiner trap

The misconception this question tests

This Context-Free Grammars and PDAs previous year question is Q10 of the GATE CSE 2017 Set 1 paper. Find more GATE CSE PYQs on Context-Free Grammars and PDAs in Theory of Computation, or browse all GATE CSE PYQs.

Free diagnostic

Where do you stand for GATE?

Take the 20-minute diagnostic: the 3 topics that cost you the most marks, and a rank range. Or sit 5 related Context-Free Grammars and PDAs PYQs now with no account.

One GATE CSE PYQ every morning

An official question by email at 7 AM IST, with a link to its verified solution. Unsubscribe in one click.

Context-Free Grammars and PDAs in GATE CSE

Context-Free Grammars and PDAs has 26 GATE CSE PYQs across 17 papers from 2011 to 2026. 9 of them are 1-mark MCQs like this one, and GATE CSE 2017 Set 1 has 3.

How GATE tests Context-Free Grammars and PDAs

More from GATE CSE 2017 Set 1

Share this solution

A plain-text card for WhatsApp or Telegram study groups.

GateAI solution cardGATE CSE 2017 Set 1 · Q10 · MCQ

Consider the following context-free grammar over the alphabet = {a, b, c} with S as the start symbol: S → abScT abcT T → bT b Which one of the following represents the language generated by the above grammar?

Topic-wise GATE CS PYQs with verified steps

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.