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.
5
-
4$\begingroup$ Try applying the pumping lemma on $a^nb^{2n}a^{2n}b^n$. $\endgroup$– Yuval FilmusCommented Jan 12, 2017 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 FilmusCommented Jan 12, 2017 at 16:55
-
$\begingroup$ See our reference question for more methods. $\endgroup$– RaphaelCommented Jan 12, 2017 at 17:29
-
$\begingroup$ @YuvalFilmus thanks, I edited the statement of the problem to clarify that $|\Sigma| > 1$ $\endgroup$– PsiCommented Jan 12, 2017 at 18:45
-
$\begingroup$ This should not be context free ,to accept this language you need more than one stack. $\endgroup$– shubham choudharyCommented Jan 13, 2017 at 3:09
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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)
