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.