Context-free grammar for an expression

Question

how to find context-free grammar for generating language

$$J={\{ba^mc^na^ma^nb}\;| n\ge1, m\ge1\} $$

I have already solved problems with constructions like $a^mc^mc^na^n$, but how to appropach the problem if the values in superscripts are "crossing", like in $a^mc^nc^ma^n$ or (simpler version) $a^nb^ma^n$?

Answer 1

Hint:

• Observe that $a^ma^n = a^{m+n}= a^na^m$, in other words $$J=\{ba^mc^na^{n+m}b\mid n\geq 1, m\geq1\}=\{ba^mc^na^na^mb\mid n\geq 1, m\geq1\}.$$
• The grammar for $\{a^nb^ma^n\mid n\geq 1, m\geq 1\}$ is \begin{align} S&\to a\ S\ a \mid a\ B\ a\\ B&\to b\ B \mid b \end{align}

I hope this helps $\ddot\smile$