Question

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

• A. $\left\{\right(a,b{)}^n(c{b}^m{)}^n|m,n\ge 1\}$
• B. $\left\{\right(a,b{)}^n(cb{)}^n|n\ge 1\}$
• C. $\left\{\right(a,b{)}^n(c{b}^n{)}^m|m,n\ge 1\}$
• D. $\left\{\right(a,b{)}^{n}c{b}^{m}1c{b}^m\mathrm{2...}c{b}^{mn}|n,m_1,m_2,...,m_n\ge 1\}$

Answer 1

The correct option is D $\left\{\right(a,b{)}^{n}c{b}^{m}1c{b}^m\mathrm{2...}c{b}^{mn}|n,m_1,m_2,...,m_n\ge 1\}$

$S\to abScT|abcT$
$T\to bT|b$
Solving T $\to b{b}^{\ast }$ will gives $b^{+}$
Substitute in S to get
$S\to abSc{b}^{+}|abcb{b}^{+}$
So, solution of S would be $\left\{\right(a,b{)}^n(c{b}^{+}{)}^n|n\ge 1\}$
Which is nothing but $\left\{\right(ab{)}^{n}c{b}^{m_1}c{b}^{m_2}....c{b}^{m_n}|n,m_1,m_2,....m_n\ge 1\}$