1
$\begingroup$

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.

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

1 Answer 1

-2
$\begingroup$

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)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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