Let $G$ be the grammar
$S \rightarrow aAb \ |$
$A \rightarrow cAc \ | \ B$
$B \rightarrow bSa \ | \ \epsilon$
over the alphabet $\{a,b,c\}$
Decide $L(G)$ (Decide the language from grammar G).
Is there any method to follow or do I just have to resort to trying strings and finding a pattern? I find the second option extremly exhausting and prone to error.
Cheers
When the grammar is simple enough, and this one definitely is, you can analyze the possible derivations.
Any derivation must start with an application of the production $S\to aAb$; after that, the only productions immediately available are the two $A$ productions. The only production that can terminate a derivation is $B\to\epsilon$, so at some point we’ll have to get a $B$. However, we can apply $A\to cAc$ any number of times before we apply $A\to B$. Thus, any derivation must begin
$$S\Rightarrow aAb\Rightarrow^n ac^nAc^nb\Rightarrow ac^nBc^nb$$
for some $n\ge 0$. At this point we can apply $B\to\epsilon$ to get the word $ac^{2n}b$, or we can apply $B\to bSa$ to get $ac^nbSac^nb$. At this point we’re basically starting over, except that whatever word is generated by $S$ this time will be sandwiched between two copies of $ac^nb$.
Suppose that we go apply $B\to bSa$ $m$ times before we finally terminate the derivation with $B\to\epsilon$. If $m=0$, we simply get $ac^{2n}b$ for some $n\ge 0$. If $m\ge 1$, we have $ac^{n_1}bSac^{n_1}b$ for some $n_1\ge 0$ after the first application of $B\to bSa$. After the second we have
$$ac^{n_1}bac^{n_2}bSac^{n_2}bac^{n_1}b$$
for some $n_1,n_2\ge 0$. After the $m$-th we have
$$ac^{n_1}bac^{n_2}b\ldots ac^{n_m}bSac^{n_m}b\ldots ac^{n_2}bac^{n_1}b$$
for some $n_1,\ldots,n_m\ge 0$, and in the end we have
$$ac^{n_1}bac^{n_2}b\ldots ac^{n_m}bac^{2n_{m+1}}bac^{n_m}b\ldots ac^{n_2}bac^{n_1}b$$
for some $n_1,\ldots,n_{m+1}\ge 0$.