edited by
21,520 views
74 votes
74 votes

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. $\{\left ( ab \right )^{n}\left ( cb \right )^{n} \mid n \geq 1 \}$
  2. $\{\left ( ab \right )^{n}cb^{m_{1}}cb^{m_{2}}...cb^{m_{n}} \mid n, m_{1}, m_{2}, ..., m_{n} \geq 1 \}$
  3. $\{\left ( ab \right )^{n}\left ( cb^{m} \right )^{n} \mid m,n \geq 1 \}$
  4. $\{\left ( ab \right )^{n}\left ( cb^{n} \right )^{m} \mid m,n \geq 1 \}$
edited by

8 Answers

Best answer
68 votes
68 votes

Answer should be B 

Consider the $1^{\text{st}}$ production $S \to abScT$

This production generates equal number of $(ab)$'s and $c$'s but after each $c$ there is $T$ which goes to $T \to bT$

So, with each $c$ there can be one or more $b$'s  (one because of production $T \to b$ and more because of $T \to bT$)

and these $b$'s are independent.

For example,

$ababcbbcbb$ is the part of the language

and $ababcbbbbbbcbb$ is also the part of the language so we can rule out options A and C as both say equal number of $b$'s after each $c.$ 

In option D equal number of $(ab)$'s and $c$'s is not satisfied. The only option that satisfies these $2$ conditions is option  B.

edited by
19 votes
19 votes

so option B is correct

edited by
5 votes
5 votes

Ans should be C) 

Minmum String : S-> abcT

                              -> abcb

S -> ab S cT

    ->ab ab S cT cT

    ->ab ab abcT cT cT

    ->ab ab ab cb cb cb

Option B) cannot be the ans as c's are without power and hence cannot be eliminated.

edited by
0 votes
0 votes
Ya its possible, confused by the condition m1,m2 greater than 1
Answer:

Related questions

44 votes
44 votes
6 answers
3
Arjun asked Feb 14, 2017
11,490 views
If $G$ is a grammar with productions$S\rightarrow SaS\mid aSb\mid bSa\mid SS\mid\epsilon$where $S$ is the start variable, then which one of the following strings is not g...