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

• Have you noticed how you tagged all your questions as [set-theory] (or [elementary-set-theory]) and how each and every one of those questions had that tag removed? – Asaf Karagila Jan 28 '13 at 22:25
• is $L = \{0^i1^i | j \ne i\}$ or $L = \{0^i1^j | j \ne i\}$ – dwarandae Jan 28 '13 at 22:26
• @dwarandae, The second option. – AnchovyLegend Jan 28 '13 at 22:28
• @Asaf, I apologize, I thought set-theory and discrete mathematics is related to this topic. While I may be wrong about set-theory, I am sure regular-languages and proofs are a subset of discrete mathematics. – AnchovyLegend Jan 28 '13 at 22:32

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.

• I appreciate the effort, however, somebody edited my post incorrectly and changed the whole meaning of the problem, the definition of language L is {0^(i)1^(j)|j≠i} (see edited) – AnchovyLegend Jan 28 '13 at 22:30
• @MHZ: The error was in your original post: you had $i$ for both exponents. And Ayman is answering the question that you meant to ask. – Brian M. Scott Jan 28 '13 at 22:33
• @MHZ Yes, my answer works for your question in its current form. – Ayman Hourieh Jan 28 '13 at 22:37
• Can you please explain how your solution works in simple terms? I am having a hard time with this one. Yes, I can prove L1 is not regular. I am not sure I understand the whole part about L2 and "what does this tell you about L=L2 - L1." I appreciate any clarification. – AnchovyLegend Jan 29 '13 at 1:41
• @MHZ If $L$ is regular, then its complement $L^\complement$ is also regular. Hence $L_2 \cap L^\complement$ is regular. But $L_2 \cap L^\complement = L_2 - L = L_1$. It follows that $L_1$ is regular, a contradiction. – Ayman Hourieh Jan 29 '13 at 1:51

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

• @Ayman: My apologies! No, I certainly don’t mind. – Brian M. Scott Jan 28 '13 at 23:06
• In your first display line, you should have $0^*1^*=\cdots$. – Rick Decker Jan 29 '13 at 13:43
• @Rick: Thanks; fixed. – Brian M. Scott Jan 29 '13 at 18:32
• Just let me add: What you are using is essentially that the words $xy^k$ are Nerode right-equivalent for each $k$, but plainly applying the MyHill-Nerode theorem it follows that for each $x,y \in X^{+}$ this must be the case from some $k \ge k_0$ onwards (without using automata), setting $y' := y^{k_0}$ we get words $x,y'$ such that $xy'^k$ are equivalent for all $k \ge 0$. – StefanH Jun 2 '16 at 17:37

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.

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.