2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I have tried for w = a^nb^naba^nb^n as the word in L. Can't prove with Pumping Lemma $\endgroup$ – Sai Manoj Kumar Yadlapati Apr 28 '13 at 9:43
  • 2
    $\begingroup$ 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$. $\endgroup$ – e_noether Apr 28 '13 at 16:07
  • 4
    $\begingroup$ @emmy Sorry, but $abab \in L$. $\endgroup$ – Hendrik Jan Apr 29 '13 at 15:25
  • $\begingroup$ @emmy You may be thinking of $\{xyx^R\ |\ |x|\ge 1\}$, which is (somewhat surprisingly when one first encounters it) regular. $\endgroup$ – Klaus Draeger Mar 1 '16 at 12:33
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

Assume $L$ was context-free. What can you say about $L \cap \mathcal{L}(a^*b^*a^*)$?

Hint: use closure properties. (That won't answer the exercise, but solve the problem.)

$\endgroup$

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