-1
$\begingroup$

Let $L$ be a given Context Free Language over the alphabet $\{a,b\}$. Now consider $$L_1=L-\{xyx\ |\ x,y\in\{a,b\}^*\}$$ I know that $\{xyx\ |\ x,y\in\{a,b\}^*\}$ is not Context Free (by using pumping lemma).

Based on that can we affirmatively say that $L_1$ will NEVER be Context Free (can't use closure property here, as $\{xyx\ |\ x,y\in\{a,b\}^*\}$ is neither CFL not Regular)?

Or shall $L_1$ ALWAYS be Context Free ?

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ Be more precise, without further conditions $\{ xyx \mid x,y\in \{a,b\}^* \}$ equals $\{a,b\}^*$. $\endgroup$
    – Hendrik Jan
    Commented Dec 10, 2013 at 15:28
  • 1
    $\begingroup$ Oh man! yes of course ... I missed that point that $x$ can be $\epsilon$. Thanks. So $\{xyx\ ∣\ x,y\in\{a,b\}^*\}$ is indeed regular without any bound on $x$ and $y$, and so is $L_1$. $\endgroup$
    – dibyendu
    Commented Dec 10, 2013 at 15:39
  • 1
    $\begingroup$ Does this answer your question? Shall we close it or should @HendrikJan post an answer? $\endgroup$
    – Raphael
    Commented Dec 10, 2013 at 18:16

1 Answer 1

Reset to default
1
$\begingroup$

Please note that $\{ xyx \mid x,y \in \{a,b\}^*\}$ is in fact equal to $\{a,b\}^*$ if no further restrictions on $x,y$ are imposed (consider $x=\varepsilon $). Then $L_1 =\varnothing$ (always) which is trivially regular.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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