1
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.
Psi
Posted 2017-01-12T16:35:57.560
Reputation: 13
-2
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)
Gal Rettig
Posted 2017-01-12T16:35:57.560
Reputation: 62
4Try applying the pumping lemma on $a^nb^{2n}a^{2n}b^n$. – Yuval Filmus – 2017-01-12T16:55:16.077
4By the way, the answer depends on the size of $\Sigma$. When $\Sigma$ is a singleton, the language is regular. – Yuval Filmus – 2017-01-12T16:55:34.337
See our reference question for more methods.
– Raphael – 2017-01-12T17:29:33.440@YuvalFilmus thanks, I edited the statement of the problem to clarify that $|\Sigma| > 1$ – Psi – 2017-01-12T18:45:51.013
This should not be context free ,to accept this language you need more than one stack. – shubham choudhary – 2017-01-13T03:09:50.387