# Prove $\{xy \mid |x|=|y|, x \neq y\}$ is not a linear language

Show the language

$$L = \{xy \mid |x| = |y|, x\neq y\}$$

is not linear.

I've seen and proved a pumping lemma for linear languages, mentioned here:

If $$L$$ is linear then there exists a constant $$p$$ such that for all $$w \in L$$ with $$|w| \ge p$$ there is a decomposition $$w = uvxyz$$ such that:

1. $$|uvyz| \leq p$$.
2. $$|vy| > 0$$.
3. $$uv^ix^iz \in L$$ for all $$i \geq 0$$.

I'm trying to find a counterexample string.

Consider this string: $$w=a^kb^ka^{2k+2k!}b^ka^k$$. We will show that we can't write this string in form of $$uvxyz$$ in a way that the conditions of pumping lemma for linear languages statisfy.

Because $$|uvyz|\leq k$$ we have : $$|uv|\leq k$$ and $$|yz|\leq k$$

So we can write: $$uv=a^{f_1}$$ , $$yz=a^{f_2}$$ , $$y=a^{g_1}$$ , $$v=a^{g_2}$$ where $$g_1+g_2>0$$ (because $$yv$$ is cannot be empty string) and $$g_1+g_2\leq k$$.

Now we pump $$v$$ and $$y$$ $$n$$-times and we have: $$w'=a^{k+ng_1}b^ka^{2k+2k!}b^ka^{k+ng_2}$$

We want to conclude this string is not in language for some $$n$$. So if we rewrite $$w'$$ as $$w'=a^{k+ng_1}b^ka^xa^{2k+2k!-x}b^ka^{k+ng_2}$$,

we should have: $$k+ng_1=2k+2k!-x$$ and $$x=k+ng_2$$

so $$k+ng_1=2k+2k!-k-ng_2 \to n(g_1+g_2)=2k! \to n=\frac{2k!}{g_1+g_2}$$.

Notice that $$g_1\leq k , g_2 \leq k \to g_1+g_2 \leq 2k$$ $$\to$$ $$g_1+g_2| 2k!$$

So we only need to set $$n=\frac{2k!}{g_1+g_2}$$ to have $$w'=w''w''$$ and this is a contradiction. So $$L$$ is not linear.

Let $$p$$ be the constant promised by the pumping lemma. Without loss of generality, $$p \geq 2$$.

Let $$w = 0^p 1 0^{2p+p!} 1 0^p$$. Since the left half of $$w$$ is $$0^p10^{p+p!/2}$$ and the right half of $$w$$ is $$0^{p+p!/2}10^p$$, we see that $$w \in L$$.

Let $$w = uvxyz$$ be the decomposition promised by the pumping lemma. Since $$|uvyz| \leq p$$, necessarily $$v = 0^j$$ and $$y = 0^k$$ belong to the first and last zero runs, respectively, and $$j+k \leq p$$. Since $$|vy| > 0$$, we have $$j+k > 0$$.

Let $$i = 1 + p!/(j+k)$$. According to the pumping lemma, $$uv^ixy^iz \in L$$. But $$uv^ixy^iz = 0^{p + jp!/(j+k)} 1 0^{2p+p!} 1 0^{p + kp!/(j+k)}.$$ The total length of this word is $$2(2p+p!+1)$$. Therefore its left half and its right half are both equal to $$0^{p + jp!/(j+k)} 1 0^{p + kp!/(j+k)},$$ showing that $$uv^ixy^iz \notin L$$, in contradiction to the pumping lemma.