Pumping Lemma Excercise I am having a really tough time proving the following language is not regular using the pumping lemma. This whole time I have been working on pumping lemma problems, the variable of the power has been the same on all alphabet characters that make up the string for the language.
$$L = \{0^i1^j | j \ne i\} $$
This is what I tried:
Let $p$ be the pumping length of $L$. Consider $S= 0^p1^j$, $|s| > p$, and $|s| > j$. Thus $s$ must satisfy the pumping lemma. Consider splitting the string:
I am assuming in order to prove this language is not regular via contradiction, we would have to find a case where the $j$ IS equal to $i$, even though they aren't supposed to be.
I am not sure how to proceed from this point of the proof and would appreciate any suggestions.
Many thanks in advance!
 A: Consider the language of all words that start with any number of $0$s followed by the same number of $1$s. You should be able to prove that this language is not regular using the pumping lemma:
$$
L_1 = \left\{0^i 1^i \mid i \ge 0 \right\}
$$
Also, consider the language of all words that start with any number of $0$s followed by any number of $1$s. This language is easily seen to be regular. Try to construct a DFA to recognize it:
$$
L_2 = \left\{0^i 1^j \mid i, j \ge 0 \right\}
$$
$L$ in the exercise is the language of all words that start with any number of $0$s followed by a different number of $1$s:
$$
L = \left\{0^i 1^j \mid i \ne j \right\}
$$
It shouldn't be difficult to convince yourself that any word in $L_1$ is also a word in $L_2$ but never a word in $L$. We can write:
$$
L_1 = L_2 - L
$$
Now, we're going to prove that $L$ is not regular by showing that a contradiction would happen if $L$ was regular.
From basic set theory:
$$
L_1 = L_2 - L = L_2 \cap L^\complement
$$
If $L$ was regular, its complement $L^\complement$ would also be regular, and the intersection $L_2 \cap L^\complement$ too. It would follow that $L_1$ would be regular. But this contradicts with the fact that $L_1$ is not regular by the pumping lemma. Therefore, $L$ cannot be regular.
A: Technically you can’t use the pumping lemma this way to prove that $L$ is not regular, because you must start with a specific word $s$. You can avoid this problem by following Ayman Hourieh’s suggestion: use it to prove that $\{0^n1^n:n\ge 0\}$ is not regular, then observe that if $L$ were regular, $$\{0^m1^n:m,n\ge 0\}\setminus L=\{0^n1^n:n\ge 0\}$$ would also be regular.
Alternatively, you can use the idea behind the proof of the pumping lemma to show that $L$ is not regular. Let $M$ be a DFA that recognizes $L$, and let $p$ be the number of states of $M$. Let $s=0^p1^{p+1}$. The proof of the pumping lemma shows that there is a decomposition $s=xyz$ such that $|xy|\le p$, $|y|\ge 1$, and $xy^kz\in L$ for all $k\ge 0$. What’s important here is the reason that $xy^kz\in L$ for all $k\ge 0$: the input string $x$ takes $M$ to some state $s_1$, and starting at $s_1$ the string $y$ then takes $M$ back to $s_1$. When $M$ reads the word $xy^kz$ this loop from $s_1$ back to $s_1$ is executed $k$ times instead of once, but since it is a loop, this has no effect on the state in which $M$ ends up on reading $xy^kz$. In particular, this means that if we change $z$ to some other string $z'$, the words $xy^kz'$ for $k\ge 0$ will all take $M$ to the same final state, and therefore either all of them will be in $L$, or none of them will be in $L$.
Let $n=|xy|\le p$; $xy$ is an initial segment of $s=0^p1^{p+1}$, so $xy$ is contained entirely in the $0^p$ part of $s$, and therefore $xy=0^n$. Let $m=|y|\ge 1$; then $|x|=n-m$, so $x=0^{n-m}$ and $y=0^m$. In fact, we can even see exactly what $z$ must be: it contains the remaining $p-n$ $0$’s and the $p+1$ $1$’s, so $z=0^{p-n}1^{p+1}$, and
$$s=xyz=\underbrace{0^{n-m}}_x\underbrace{0^m}_y\underbrace{0^{p-n}1^{p+1}}_z\;.$$
Now
$$xy^kz=\underbrace{0^{n-m}}_x\underbrace{0^{km}}_{y^k}\underbrace{0^{p-n}1^{p+1}}_z\;,$$
which has $(n-m)+km+(p-n)=p+(k-1)m$ $0$’s and $p+1$ $1$’s. There’s no contradiction here, because it’s quite possible that $(k-1)m\ne 1$ for all $k\ge 0$. However, we can let $z'=0^{p-n}1^{p+m}$ and note that by the earlier observation, either all of the words $xy^kz'$ are in $L$, or none of them is. And this does give us a contradiction, because $xy^kz'$ has $p+(k-1)m$ $0$’s and $p+m$ $1$’s, and these two numbers are equal when $k=2$ and unequal otherwise. That is, $xy^2z'\in L$, but $xyz'\notin L$.
A: Let me add a simple proof just using the plain pumping lemma.
Suppose $L = \{0^i0^j \mid i \ne j \}$ is regular and let $N$ be the pumping constant. Set $k := \operatorname{lcm}(1,2,\ldots, N)$ and consider $w = 0^k1^{2k}$. Surely $|w| \ge N$, hence we have $w = xyz$, and as $|xy| \le N \le k$ we have $y = 0^l$ with $1 \le l \le N$, hence there exists $m$ such that $ml = k$. Now consider
$$
 xy^{m+1}z = 0^{k+ml}1^{2k} = 0^{2k}1^{2k} \notin L.
$$
I have seen people claiming this language fulfills the conclusions of the pumping lemma, so it might be good to have the above proof here. Also note that it uses the "weak" form without "zero"-pumping as it is sometimes (but of course rarely) found in lecture notes.
A: Let's assume that $L$ is regular, and let $n$ be the pumping constant.
Take $z = 0^n1^{n+n!}$.
$|z| \geq n$, so according to the lemma, $z$ can be written as $uvw$ where $|uv| \leq n$, $|v|\geq1$, and for each $i\in\mathbb{N}$, $uv^iw\in L$.
Since $|uv| \leq n$, we can write $z$ as $u=0^l, v=0^t, w=0^{n-l-t}1^{n+n!}$, where $1\leq t\leq n$ (since $|v|\geq 1$), so for each $i$ we know that $z_i= uv^iw=0^l0^{it}0^{n-l-t}1^{n+n!}=0^{n+t(i-1)}1^{n+n!}\in L$.
Now take $i_0=\frac{n!}{t}+1$. we know that this $i_0$ is a natural number since $1\leq t\leq n$, so according to the lemma $z_{i_0} = 0^{n+t((\frac{n!}{t} +1)-1)}1^{n+n!}=0^{n+n!}1^{n+n!}\in L$, contradiction.
