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$ – emmy 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$

protected by Community May 6 '17 at 18:08

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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