0
$\begingroup$

Im trying to prove that $L=\{w\#s : |w|=|s|, w \neq s\} \notin CFL$ using the pumping lemma. So I said, let say $L \in CFL$ so by the pumping exists $p$ which is the pumping length of language $L$, I think $ s = 0^{m}1^{p}\#1^{m}0^{p} \in L$ would be a good word to start with, I can write $s = uvxyz$ and i want $uv^{i}xy^{i}z\notin L$ i want somehow to force the new word to Not contain $'\#'$ or $|w|\neq |s|$. The first option could be achived if ill make sure $'\# \in v\cup y$ and ill just choose $i=0$. And for the second option, i want to force $|v|\neq |y|$ and then for every $i$ it will be good.

But i cant see how to analyize the word fulfills the requirements.

Edit:

I think it isnt a duplicate question, This language isnt context free as mention in the comments.

The $"\#"$ char is the thing that make the difference between the language that was suggested as a duplicate post.

I've succsed to prove it by the pumping lemma when choosing the word $w = 0^{p!+p}1^{p}\#0^{p}1^{p!+p}$ and $i=1+\frac{p!}{t}$ to pump with in the non trivial part where $w=uvxyz$ is the partition and $|v|=|y|, v\subseteq w $ and $ y\subseteq s$ , this way ill get that $uv^{i}xy^{i}z=w\#s$ where $w=s$

Full proof : (more rigorous proof to this question than mine)

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$
  • 1
    $\begingroup$ what kind of strings are $m$ and $s$? If $m, s \in \{0,1\}^*$ I think it will be impossible to prove that this language is not context free. $\endgroup$ – abc Apr 8 '17 at 14:16
  • $\begingroup$ @newbie You are right $m,s \in \{0,1\}^{*}$ i forgot to say it. $\endgroup$ – limitless Apr 8 '17 at 14:37
  • $\begingroup$ The L from the title or the L from the text? Hint: both are context-free. $\endgroup$ – Raphael Apr 8 '17 at 15:13
  • $\begingroup$ This is a nice, but fairly standard exercise, and one we've covered before. I'm linking you the duplicates, but I suggest you honestly try to solve it yourself. It's very good problem! $\endgroup$ – Raphael Apr 8 '17 at 15:22
  • 1
    $\begingroup$ So we have a proof that the language is context-free, and one for that it is not. One must be wrong. $\endgroup$ – Raphael Apr 29 '17 at 15:28