Given a finite alphabet $\Sigma$ with more than one symbol, is $L = \{u u^R u : u \in \Sigma^*\}$ context-free? ($u^R$ is the reverse word of $u$)

I tried to show it wasn't context-free by using the pumping lemma but I'm out of ideas.

  • 4
    $\begingroup$ Try applying the pumping lemma on $a^nb^{2n}a^{2n}b^n$. $\endgroup$ – Yuval Filmus Jan 12 '17 at 16:55
  • 4
    $\begingroup$ By the way, the answer depends on the size of $\Sigma$. When $\Sigma$ is a singleton, the language is regular. $\endgroup$ – Yuval Filmus Jan 12 '17 at 16:55
  • $\begingroup$ See our reference question for more methods. $\endgroup$ – Raphael Jan 12 '17 at 17:29
  • $\begingroup$ @YuvalFilmus thanks, I edited the statement of the problem to clarify that $|\Sigma| > 1$ $\endgroup$ – Psi Jan 12 '17 at 18:45
  • $\begingroup$ This should not be context free ,to accept this language you need more than one stack. $\endgroup$ – shubham choudhary Jan 13 '17 at 3:09

Based on : Pumping Lemma for Context-Free Languages for reversal language

By @lukas.coenig

{ww$^R$w| w $\in$ {a,b}*} doesn't seem to be a context-free language over $\Sigma$ of length two.

Assuming this language isn't context free over an alphabet of size 2 to prove it also over size of 3.. and so on by induction might be interesting..(and if true by induction than there is probably a better way to prove it)


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.