GATE CSE 2017 Set 1 | Question: 10

Question

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?

• A. $\{\left ( ab \right )^{n}\left ( cb \right )^{n} \mid n \geq 1 \}$
• B. $\{\left ( ab \right )^{n}cb^{m_{1}}cb^{m_{2}}...cb^{m_{n}} \mid n, m_{1}, m_{2}, ..., m_{n} \geq 1 \}$
• C. $\{\left ( ab \right )^{n}\left ( cb^{m} \right )^{n} \mid m,n \geq 1 \}$
• D. $\{\left ( ab \right )^{n}\left ( cb^{n} \right )^{m} \mid m,n \geq 1 \}$

Comments

Language in Option C is subset of Language in Option B & So, Language in option C is not able to produce all & only strings produced by the given CFG, so correct answer is Option B

---

Grammar in Option C is subset of grammar in Option B & Grammar in option C is not wrong, it is just unable to produce some more strings which are generated by Grammar in Option B

@pratik2404

Option C is Wrong language for the given grammar.

A grammar $G$ generates language $L$ If and Only If $\color{red}{\text{All & Only}}$  the strings of $L$ are generated by $G.$

Grammar in option C is not wrong, it is just unable to produce some more strings which are generated by Grammar in Option B

By this logic, Saying “$\phi$ is the language generated by every CFG $G$” would not be wrong.

So, this logic is wrong.   

---

@Deepak Poonia Sir, Yes You are right, option C is completely wrong and I am not defending option C, I’m just saying that difference in option B and option C is only that in Option C we fixed b^m means along with every c same number of b’s are coming but our grammar is able to produce same as well as different number of b’s along with c , so every string produce by language in option C is accepted by given CFG but it is not able to produce all the strings & all the strings will be produced by only option B. So, option C is completely wrong and option B is the only right answer. Actually, my statement becomes ambiguous :) Ok I will edit it.

Answer 1

T→ bT | b, this production will generate any number of b’s > 1
S→ abScT | abcT, this production will generate equal number of “ab” and “c” and for every “abc” any number of b’s ( > 1) after “abc”.
For Ex:

Hence the language generated by the grammar is
L = {(ab)n cb(m1 ) cb(m2 )…cb(mn )│n,m1,m2,…,mn ≥ 1}

Answer 2

B is answer.

Option A, C and D all can generate the strings where may have 2 occurrences of C but given grammar has a restriction on this, c B c B..

Answer 3

Just expand the tree and derive the string. Option B is the best expression for the language.

Answer 4

Option B is correct

Comments

Why? How please give some example

---

@Sandeep

You can refer the 1st answer, it is well explained.