L is language generated by the context free grammar G = (V, $\Sigma$, P, S)

Question

L is language generated by the context free grammar G = (V, $\Sigma$, P, S), where $\Sigma$ = {a,b,c}, V = {S, A, B}, and the production set P is:

S -> aSb | A

A -> cAb | B

B -> cb

My question is, can the following belong to L?

accbbbcb?

i think it does because:

accbbb = S -> aSb -> acBbb -> accbbb cb = B -> cb so, concatenating both, accbbbcb.

Maybe this is a too elementary question, but just wanted to check. Thank you!

Answer 1

$\newcommand{\aa}{\mathtt{a}}\newcommand{\bb}{\mathtt{b}}\newcommand{\cc}{\mathtt{c}}$No, $\aa\cc\cc\bb\bb\bb\cc\bb$ does not belong to $L$. Your concatenation does not make sense. Your language is $$ L = \{\aa^i\cc^k\cc\bb\bb^k\bb^i \mid i \leq 1 \} = \{\aa^i\cc^{k+1}\bb^{k+i+1} \mid i \leq 1\}. $$

Observe, that the letters appear sorted: $\aa$, $\cc$ and then $\bb$, so $\aa\cc\cc\bb\bb\bb$ could be an element of $L$ (and it is, as you already proved), but $\aa\cc\cc\bb\bb\bb\cc\bb$ could not (and it is not).

I hope this helps $\ddot\smile$