Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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

2 Answers 2

up vote 4 down vote accepted

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.

share|improve this answer
    
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
3  
@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$.

share|improve this answer
    
+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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.