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.

Improve this question
$\endgroup$
4
  • $\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
    Commented Apr 28, 2013 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
    Commented Apr 28, 2013 at 16:07
  • 4
    $\begingroup$ @emmy Sorry, but $abab \in L$. $\endgroup$
    – Hendrik Jan
    Commented Apr 29, 2013 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
    Commented Mar 1, 2016 at 12:33

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I've been trying a lot, that example doesn't work for this problem. In fact, I think pumping lemma isn't solving it either $\endgroup$
    – Seven
    Commented Apr 7, 2020 at 15:46
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.)

Improve this answer
$\endgroup$
0

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