Consider the following context-free grammar over the alphabet \(\Sigma =…
2017
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 \}\)
Attempted by 72 students.
Show answer & explanation
Correct answer: B
Key idea: each recursive use of S -> ab S c T adds one "ab" at the left and one "cT" at the right; the base S -> abcT provides the final "ab c T". Each T produces b^m with m ≥ 1 independently.
Base case (n = 1): S -> abcT -> ab c b^{m1}, giving (ab)^1 c b^{m1} with m1 ≥ 1.
Recursive step: one application S -> ab S c T adds an "ab" to the left and another "cT" to the right. After n applications you get (ab)^n followed by n copies of c each followed by an independent b^{mi} from the corresponding T.
Therefore the generated language is strings of the form (ab)^n c b^{m1} c b^{m2} ... c b^{mn} with n ≥ 1 and each mi ≥ 1, which matches the given option (ab)^n cb^{m1}cb^{m2}...cb^{mn}.
A video solution is available for this question — log in and enroll to watch it.