Pumping Lemma Excercise

Question

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!

Answer 1

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.

Answer 2

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$.