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.

  • $\begingroup$ 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) $\endgroup$ – Hendrik Jan Dec 16 '13 at 11:15
  • $\begingroup$ @HendrikJan It's almost the same only without the $z$ part. $\endgroup$ – Yuval Filmus Dec 16 '13 at 11:21
  • $\begingroup$ @YuvalFilmus Yes, can you give any hint about his exercise 2? I don't have enough reputation to comment in that question. $\endgroup$ – sjtufs Dec 16 '13 at 11:31
  • $\begingroup$ @YuvalFilmus Sorry, I missed the $z$ part. Now I am curious what "theorem given in textbook" is relevant for this language? $\endgroup$ – Hendrik Jan Dec 16 '13 at 11:59
  • $\begingroup$ @HendrikJan Almost the same with exercise given by Raphael in his answer to that old question $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.