Consider the following context-free grammar over the alphabet \(\Sigma =…

PYQ GATE 2017

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?

  1. A.

    {(ab)n(cb)n∣n≥1}\{\left ( ab \right )^{n}\left ( cb \right )^{n} \mid n \geq 1 \}

  2. B.

    {(ab)ncbm1cbm2...cbmn∣n,m1,m2,...,mn≥1}\{\left ( ab \right )^{n}cb^{m_{1}}cb^{m_{2}}...cb^{m_{n}} \mid n, m_{1}, m_{2}, ..., m_{n} \geq 1 \}

  3. C.

    {(ab)n(cbm)n∣m,n≥1}\{\left ( ab \right )^{n}\left ( cb^{m} \right )^{n} \mid m,n \geq 1 \}

  4. D.

    {(ab)n(cbn)m∣m,n≥1}\{\left ( ab \right )^{n}\left ( cb^{n} \right )^{m} \mid m,n \geq 1 \}

Attempted by 124 students.

Sign up free to check your answer

Sign up free

Explore the full course: Theory Of Computation

Loading lesson…