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

-
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. –  Epsilon 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. –  Epsilon 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) –  Epsilon 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. –  Epsilon 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$.

-
+1, I corrected my last name (if you don't mind). :) –  Ayman Hourieh Jan 28 '13 at 23:04
@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