# Is {xyx | |x|≥1} context-free?

Is $L=\{ xyx \mid x,y \in \{a,b\}^* \text {and } |x| \ge 1 \}$ context-free?

If yes, please explain how we can write grammar or create a PDA for it. If not a CFL, then prove it through pumping lemma.

I have tried to apply the pumping lemma with $w = a^nb^naba^nb^n$ as the word in $L$, but without success.

• I have tried for w = a^nb^naba^nb^n as the word in L. Can't prove with Pumping Lemma – Sai Manoj Kumar Yadlapati Apr 28 '13 at 9:43
• Isn't it regular? For a word $w$ check if the first letter is equal to the last letter; if yes, $w \in\ L$,else $w\notin\ L$. As there is no restriction on y, y can have length $|w|-2$. – e_noether Apr 28 '13 at 16:07
• @emmy Sorry, but $abab \in L$. – Hendrik Jan Apr 29 '13 at 15:25
• @emmy You may be thinking of $\{xyx^R\ |\ |x|\ge 1\}$, which is (somewhat surprisingly when one first encounters it) regular. – Klaus Draeger Mar 1 '16 at 12:33

Consider $w = a^nb^na^nb^n$, then it is similar to proving language {ww} is not CFL.
In the given language there is no restriction on length of y. So, let it be zero. Now, for any valid decomposition w = uvxyz, $uv^ixy^iz$ belongs to L.
Assume $L$ was context-free. What can you say about $L \cap \mathcal{L}(a^*b^*a^*)$?