Formal grammar for the language $L = \{w\in\{a,b\}^*,\,w=xx,\,x=a^nb^na^mb^m,\,n\ge0,\,m\ge0\}$

Question

What is the grammar of this language?

$$L = \{w\in\{a,b\}^*,\,w=xx,\,x=a^nb^na^mb^m,\,n\ge0,\,m\ge0\}$$

For example: $abab$, $abaabbabaabb$

Answer 1

I think you need to do it in two steps: First a grammar to generate your $x$, or actually strings of the form $Xu^nv^nu^mv^mY$. You can easily adapt the grammar we discussed in the above comments to make these strings. Now you need to create a copying machine to duplicate the string. I used $u$ and $v$ instead of $a$ and $b$ here, intending to convert them to $a$ and $b$ as the copying progresses. Here is a set of productions to achieve this: $$\begin{aligned} X&\rightarrow XR&Ra&\rightarrow aR&Rb&\rightarrow bR&RY&\rightarrow\varepsilon\\ Ru&\rightarrow Ua&Rv&\rightarrow Vb&XU&\rightarrow XaR&XV&\rightarrow XbR\\ aU&\rightarrow Ua&bU&\rightarrow Ub&aV&\rightarrow vA&bV&\rightarrow Vb\\  \end{aligned}$$ The set is not complete yet! But look: $X$ can spawn an $R$ which moves right past all $a$s and $b$s until it hits a $u$ or $v$, where it converts that to $a$ or $b$ and morphs into $U$ or $V$, which travels left until it hits $X$, where it becomes $a$ or $b$ – that is the copy – and a new $R$ to travel right and continue the process.

You may need a few more productions to finish it off. Perhaps you only need to add $X\rightarrow\varepsilon$ to finish the job.

This is a lot like programming. Think of the nonterminals as little special purpose machines traveling back and forth doing their thing.

Finally, a disclaimer: I have not debugged the above! There may well be bugs, like in any program. I will leave the debugging and verification to you. Good luck.