0
$\begingroup$

Let $"x"$ and $"y"$ be a words, we will say that two words are "completely different" if for all $1\leq i\leq |x|$ the $i$ letter in $x$ diffrent from the $i$ letter in $y$.

Prove that the language $\mathscr{L}=\{xy \mid x,y\in \{0,1\}^*,|x|=|y|,x,y \text{ completely different} \}$ is not a free-context-language

I need some hints please about choosing the word for applaying the pumping lemma, I tried $0^n1^n$ but it did not work well

$\endgroup$
2
$\begingroup$

If $p$ is the proposed pumping length, try the word $0^p1^p0^p1^p0^p1^p$. Note that if it is decomposed as $uvwxy$ as in the Pumping Lemma, then as $| vwx | \leq p$ this substring is either part of a $0^p$ or part of a $1^p$ or straddles a $0^p1^p$ or straddles a $1^p0^p$. Argue based on positioning that pumping zero times results in a string not in the language.

$\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.