3
$\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)

$\endgroup$
  • $\begingroup$ actually, the language is not context-free $\endgroup$ – Phumb Dec 5 '12 at 18:54
  • $\begingroup$ Is this language Context sensitive ? $\endgroup$ – Garrick Oct 9 '16 at 17:53
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.
$\endgroup$
  • $\begingroup$ Yup, this makes sense. I couldn't find a string that works before. Thank you. $\endgroup$ – Phumb Dec 6 '12 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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