2
$\begingroup$

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.

$\endgroup$

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.