9
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

Your proof is correct, and I was wrong. It took me a while to nail down where my confusion was, but with Yuval's help I think I got it.

Let's consider the three languages

$\qquad\begin{align*} &L_= &\!\!\!\!\!\!\!\!\! &= \{ xy \mid |x| = |y|, x \neq y \}, \\ &L_{\#} &\!\!\!\!\!\!\!\!\! &= \{ x\#y \mid x \neq y \},\ \text{and} \\ &L_{=\#} &\!\!\!\!\!\!\!\!\! &= \{ x\#y \mid |x| = |y|, x \neq y \}. \end{align*}$

As we have seen here, $L_=$ is context-free. The trick is, in the grammar, to generate symbols "on the right" but count them "on the left" later (or the other way around), making sure mismatching symbols appear at matching positions. The length condition is trivial since it reduces to even length.
You can construct an NPDA with a similar idea, using the stack to match the position.

$L_\#$ is also context-free. The proof is even simpler: the mismatching symbols appear the same distance away from the beginning resp. the separator. Unequal lengths can be checked separately; non-determinism "chooses" between the two options.

Now, as you show, $L_{=\#}$ is not context-free. Here is why the proofs for the other two languages break down.

  1. In the grammar for $L_=$, if we have to generate a separator in the middle we can not "reassign" symbols from "left" to "right".
  2. Instead of "accept if lengths unequal or mismatch" we have to "accept if lengths equal and mismatch". Non-determinism can not help us with the and!

So what it boils down to, intuitively, is that conditions of the form "$x \neq y$" and "$|x| = |y|$" are both "context-free" in the sense that they can be checked with a stack, but not using finite control. Therefore, a PDA can do one but not both.

The PDA for $L_=$ "cheats" since it does not really check these conditions for $x$ and $y$; it splits the word up in a different way. That's no longer possible if you have the separator.


Addendum: I boldly claimed that $L_= \in \mathrm{CFL} \implies L_{=\#} \in \mathrm{CFL}$ because CFL is closed against inverse homomorphism. While it's true that $f(L_{=\#}) = L_=$ with $f$ the identity except it deletes $\#$, that is not relevant. $f^{-1}(L_=) = L_\#$; nothing can be said about $L_{=\#}$.


Addendum II: Note that $L = \{ x\#y \mid |x| = |y| \}$ is trivially context-free. Hence, with $L \cap L_\# = L_{=\#}$ we have a nice example for CFL not being closed against intersection.

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