Is this language regular? $\{0^n 1^m \mid m \ne n\}$, I don't understand the direct proof by pumping length

312 Views Asked by At

There is a direct way to prove it: If $p$ is the pumping length and we take the string $s = 0^{(p)}1^{(p+p!)}$, then no matter what the decomposition $s = xyz$ is the string $xy^{(1+p!/|y|)}z$ will equal $0^{(p+p!)}1^{(p+p!)}$ which is not in the language.

I don't understand the value $y$ given here.

1

There are 1 best solutions below

2
On BEST ANSWER

The pumping lemma says that if a language $L$ is regular, there is a length $p$, the pumping length, such that whenever $s\in L$ and $|s|\ge p$, it is possible to split $s$ as $xyz$ in such a way that $|y|\ge 1$, $|xy|\le p$, and $xy^kz\in L$ for every non-negative integer $k$.

Suppose that $L=\{0^n1^m:m\ne n\}$ is regular, and let $p$ be its pumping length. Let $s$ be the word $0^p1^{p+p!}$ consisting of $p$ zeroes followed by $p+p!$ ones; $p\ne p+p!$, so $s\in L$, and $|s|=2p+p!$, which is certainly greater than or equal to $p$. Now suppose that we’ve split $s=xyz$ as in the pumping lemma. In particular the front part $xy$ has length at most $p$. And the first $p$ symbols of $s$ are all zeroes, so $xy$ must be a string of zeroes. Say that $x=0^i$ and $y=0^j$; what we know is that $i+j=|xy|\le p$, and $j=|y|\ge 1$. Thus, $j$ must be one of the integers $1,2,\ldots,p$, which means that $p!$ is divisible by $j$. Let $n=\frac{p!}j$; then

$$y^{1+n}=(0^j)^{1+n}=0^{j+jn}=0^{j+p!}\;,$$

so

$$xy^{1+n}=0^i0^{j+p!}=0^{i+j+p!}\;.$$

Now let’s get back to $z$: it’s all of $s$ except the $i+j$ zeroes in $xy$, so it’s $0^{p-(i+j)}1^{p+p!}$. But this means that

$$xy^{1+n}z=0^{i+j+p!}0^{p-(i+j)}1^{p+p!}=0^{p+p!}1^{p+p!}\;,$$

which is not in $L$. Thus, there is no decomposition of $s$ satisfying the conclusion of the pumping lemma, and therefore $L$ cannot be regular after all.