# Is $\{u u^R u : u \in \Sigma^*\}$ context-free?

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.

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

## 1 Answer

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)