4
$\begingroup$

Is the language $L=\{ xyx^Ry^R \mid x,y \text{ is an element of }\{0,1\}^*\}$ context-free?

Note: $x^R$ is the reverse of $x$.

My Work: I think this is a context free language. Since a pushdown automaton (PDA) accepts context-free languages, I am trying to draw a PDA for this language. When I draw a PDA, how does the PDA tell $x$ and $y$ apart? Or is this not a context-free language? (then I can use pumping length to prove this)

Improve this question
$\endgroup$
2
  • $\begingroup$ actually, the language is not context-free $\endgroup$
    – Phumb
    Dec 5, 2012 at 18:54
  • $\begingroup$ Is this language Context sensitive ? $\endgroup$
    – Garrick
    Oct 9, 2016 at 17:53

2 Answers 2

Reset to default
4
$\begingroup$

No, it is not a context-free language. From my original SO answer: consider the string $0^n1^n0^n1^n \in L$, where $n$ is the pumping length from the pumping lemma for context-free languages. This fails the pumping lemma for context-free languages; in particular, we have seven cases for $vxy$:

  1. $vxy$ consists entirely of 0s from the first part of the string. Pumping this up or down will cause the numbers of 0s in the first and third parts of the strings to be different, so we're no longer in $L$.
  2. $vxy$ consists entirely of 1s from the second part of the string. Same problem between the second and fourth parts as between the first and third parts mentioned in case 1.
  3. $vxy$ consists entirely of 0s from the third part of the string. Same but opposite problem as in case 1.
  4. $vxy$ consists entirely of 0s from the fourth part of the string. Same but opposite problem as in case 2.
  5. $vxy$ straddles the first and second parts of the string, beginning with 0s and ending with 1s. Pumping will change the the numbers of 0s and 1s in the first and second parts of the string, and they won't match the third and fourth parts of the string anymore, so we're not in $L$ anymore.
  6. $vxy$ straddles the second and third parts of the string, beginning with 1s and ending with 0s. We have the same problem as in case 5.
  7. $vxy$ straddles the third and fourth parts of the string, beginning with 0s and ending with 1s. We have the same but opposite problem as in case 5.
Improve this answer
$\endgroup$
1
  • $\begingroup$ Yup, this makes sense. I couldn't find a string that works before. Thank you. $\endgroup$
    – Phumb
    Dec 6, 2012 at 22:12
3
$\begingroup$

The language is not context-free. This can be shown with help of the the context-free pumping lemma. Let $p$ be the pump width, then show that is not possible to "pump" the word $w=1^p0^p1^p0^p$.

You are left with showing the following. No matter how one subdivides $w$ into 5 parts $u,v,x,y,z$ with $|vy|>0$ and $|uxy|\le p$, there exists for every such subdivision some $i$, such that $uv^ixy^iz\not\in L$. Use a case distinction.

Improve this answer
$\endgroup$

Your Answer

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

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