# How can ws with |w| = |s| and w ≠ s be context-free while w#s is not?

Why does (if so) the seperator $$\#$$ is making a difference between the two languages ?

Let say:

$$L=\{ws : |w|=|s|\, w,s\in \{0,1\}^{*}, w \neq s \}$$

$$L_{\#}=\{w\#s : |w|=|s|\, w,s\in \{0,1\}^{*}, w \neq s \}$$

Here is a proof and a grammer representing $$L$$ as a $$CFL$$

And below Im adding a proof for $$L_{\#} \notin CFL$$ :

Does the $$\#$$ sign truly make a difference? if so, why is that ? and if not, which one of the proofs is wrong and where?

## Proof that $$L_{\#} \notin CFL$$ :

Assume by way of contradiction that $$L ∈ CFL$$. Let $$p > 0$$ be the pumping constant for $$L$$ guaranteed by the pumping lemma for context-free languages. We consider the word $$s = 0^{m}1^{p}\#0^{p}1^{m}$$ where $$m=p!+p$$ so $$s ∈ L$$. Since $$|s| > p$$, according to the pumping lemma there exists a representation $$s = uvxyz$$, such that $$|vy| > 0$$, $$|vxy| ≤ p$$ , and $$uv^{j}xy^{j} z ∈ L$$ for each $$j ≥ 0$$.

We get a contradiction by cases:

• If $$v$$ or $$y$$ contain $$\#$$: Then for $$i = 0$$, we get that $$uxz$$ does not contain $$\#$$, so $$uxz \notin L$$ in contradiction.
• If both $$v$$ and $$y$$ are left to $$\#$$: Then for $$i = 0$$, we get that $$uxz$$ is of the form $$w\#x$$, where $$|w| < |x|$$, so $$uxz \notin L$$.

• If both $$v$$ and $$y$$ are right to $$\#$$: Similar to the last case.

• If $$v$$ is left to $$\#$$, $$y$$ is right to it, and $$|v| < |y|$$: Then for $$i = 0$$, we get that $$uxz$$ is of the form $$w\#x$$, where $$|w| > |x|$$, so $$uxz \notin L$$.

• If $$v$$ is left to $$\#$$, $$y$$ is right to it, and $$|v| > |y|$$: Similar to the last case.

• If $$v$$ is left to $$\#$$, $$y$$ is right to it, and $$|v| = |y|$$: This is the most interesting case. Since $$|vxy| ≤ p$$, $$v$$ must be contained in the $$1^{p}$$ part of $$s$$, and $$y$$ in the $$0^{p}$$ part. So it holds that $$v = 1^{k}$$ and $$y = 0^{k}$$ for the same $$1 ≤ k ≤ p$$ (in fact, it must be that $$k < p/2$$). For each $$j ≥ 0$$, it holds that $$uv^{j+1}xy^{j+1}z = 0^{m}1^{p+j·k}\#0^{p+j·k}1^{m}$$, so if it happens that $$m = p + j · k$$, then it holds that $$uv^{j+1}xy^{j+1}z \notin L$$ in contradiction. To achieve this, we must take $$j = (m-p)/k$$, which is valid only if $$m − p$$ is divisible by $$k$$. Recall that we chose $$m = p + p!$$, so $$m − p = p!$$, and $$p!$$ is divisible by any $$1 ≤ k ≤ p$$ as wanted.

Posted on Categories proxiesTags