# Looking for a contex-free grammar for the following language

I want to derive a context free grammar for the following language on alphabet $\Sigma=\{a,b\}$:

$\qquad\displaystyle \{ xax'yby'z \mid x,y,z\in\Sigma ^*, |x|=|x'|, |y|=|y'|, |z|=|x|+|y|\}$

I am convinced that this language is context-free because this is part of my proof to a theorem given in textbook, but haven't yet seen a context-free grammar for it.

• Look at this old question Show that {xy∣|x|=|y|,x≠y} is context-free which is almost the same (except that a,b may swap positions there) – Hendrik Jan Dec 16 '13 at 11:15
• @HendrikJan It's almost the same only without the $z$ part. – Yuval Filmus Dec 16 '13 at 11:21
• @YuvalFilmus Yes, can you give any hint about his exercise 2? I don't have enough reputation to comment in that question. – sjtufs Dec 16 '13 at 11:31
• @YuvalFilmus Sorry, I missed the $z$ part. Now I am curious what "theorem given in textbook" is relevant for this language? – Hendrik Jan Dec 16 '13 at 11:59
• @HendrikJan Almost the same with exercise given by Raphael in his answer to that old question – sjtufs Dec 16 '13 at 12:16

Hint: you want to measure size of $x$ and $y$, and still have the sum of the two in the end. so when you read them, you will need twice their size: one for $x'$, and one for $z$. Start with designing a PDA, it seems easier than a grammar. Then you can use a PDA-to-grammar translation to get the wanted grammar.