Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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)

share|improve this question
    
actually, the language is not context-free –  Phumb Dec 5 '12 at 18:54

2 Answers 2

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.
share|improve this answer
    
Yup, this makes sense. I couldn't find a string that works before. Thank you. –  Phumb Dec 6 '12 at 22:12

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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