Find a context-free grammar for uc^nd^nv where the number of a's and b's in uv are equal

Question

I want to construct a context-free grammar for this language:

\begin{align*} L = \{uc^nd^nv\mid \ u,v \in \{a,b\}^* \text{ and the number of a's and b's in } uv \text{ are equal}\} \end{align*}

I know how to contruct a grammar for a language that has words with an equal number of a's and b's: \begin{align*} &S\to aSb \\ &S\to bSa \\ &S\to SS \\ &S\to \epsilon \end{align*} I also know how to construct $c^nd^n$: \begin{align*} &S\to cSd \\ &S\to \epsilon \end{align*} Could you give any hints how to combine these rules?

Answer 1

Consider the following operation on context-free languages. For $L\subseteq \{a,b\}^*$, we have $L_\square = \{ u\square v \mid uv\in L\}$, where $\square$ is a new symbol. Thus $L_\square$ adds a single symbol $\square$ at an arbitrary position in the strings of $L$. That position of $\square$ can be used for the axiom to "insert" another language in your strings, by putting the axiom of this other language at that position.

How do we add a single new symbol? By tracing a path in the derivation tree, using "marked" copies of the original nonterminals, until one of these marked copies "drops" the symbol $\square$ in the string.

In your specific case that means introducing productions like $\hat S\to a\hat Sb$, $\hat S\to \hat SS$, $\hat S\to S\hat S$, $\hat S\to \square aSb$, $\hat S\to a\square Sb$ and more.