# 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 Apr 28, 2013 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$. Apr 28, 2013 at 16:07
• @emmy Sorry, but $abab \in L$. Apr 29, 2013 at 15:25
• @emmy You may be thinking of $\{xyx^R\ |\ |x|\ge 1\}$, which is (somewhat surprisingly when one first encounters it) regular. Mar 1, 2016 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^*)$?