I need to proof by using the Pumping lemma that the language $L = \{0^m1^n \;|\; m \geq n\}$ is not regular.

According to the Pumping lemma for each regular language a word $w = xyz$ exists, that $$\forall n,k \in \mathbb{N} \text{ with } 0 < |y| \leq |xy| \leq n$$ applies: $$xy^kz \in L$$

I'm not sure how to build the word w. This is what I've tried:

$$w = 0^n1^{n-1}, x = \lambda, y = 0^n \Rightarrow |xy| = n \leq n$$ (condition of Pumping lemma).

If I set k to $0$ I get $$w = xy^0z = xz = \lambda z = z = 1^{n-1} \not\in L$$ because $$|_1w| = n-1 > |_0w| = 0 $$ $\Rightarrow L $ ist not regular.

The only restriction for my proof is $k > 0$.

Is this right? Thanks in advance!


Think of the Pumping Lemma as a game in which you're trying to prove that a language isn't regular, while someone else is "defending" the regularity of this language. Here is how to play the game:

  1. The defender specifies the pumping length $n$. Think of it as the number of states in the automata that recognizes the language.
  2. You give the defender a word $w$ from the language that satisfies the condition: $|w| \ge n$.
  3. The defender divides this word into $xyz$, where $|xy| \le n$ and $|y| > 0$. This division must also satisfy the condition that $xy^{k}z$ belongs to the language $\forall k \ge 0$.

If you give the defender a word that is impossible to divide under the conditions in step 3, you win and the language isn't regular.

Given the above, let's have a look at your answer. You gave the word $0^{n}1^{n-1}$. I'll play the role of the defender and divide it as: $0^{n-1}01^{n-1}$ where $x = 0^{n-1}$, $y = 0$ and $z = 1^{n-1}$. This division satisfies all of the conditions above:

  • $|xy| = |0^n| \le n$
  • $|y| = |0| = 1 \ge 0$
  • $xy^{k}z = 0^{n-1}0^{k}1^{n-1} = 0^{n+k-1}1^{n-1} \in L$

The last condition is justified because:

$$ k \ge 0 \Rightarrow n+k-1 \ge n-1 $$

Thus, your word doesn't make it impossible for me to divide the word in a way that satisfies the Pumping Lemma's conditions.

Now, what if we consider $0^{n}1^{n}$ instead? No matter how I divide it, $x$ and $y$ will always fall within the $0^n$ part since $|xy| \le n$. Therefore, $y$ will consist of one or more $0$s. For $k = 0$, one or more $0$s will be removed and the number of $0$s in the string will be less than the number of $1$s, and the word will no longer be in the language. Hence, the language isn't regular.

  • $\begingroup$ great explanation - thank you! $\endgroup$ – muffel May 30 '12 at 21:20
  • $\begingroup$ $k=0$ is a possibility often missed. $\endgroup$ – Raphael May 31 '12 at 11:00

That's not quite right. Think of the pumping lemma as a game:

  • Mr. Pumping Lemma gives you a constant $n$.
  • You choose a word $w$ in the language of length at least $n$.
  • Mr. Pumping Lemma gives you $x$, $y$, and $z$ with $xyz=w$, $|xy|≤n$, and $y$ not empty.
  • Now you pick $r$.
  • Mr. Pumping Lemma asserts that $xy^rz$ is also in the language.
  • If he's wrong, you win.

In your question, it seems that once you picked $w$, you went ahead and chose $x$ and $y$. You don't get to do this. That is Mr. Pumping Lemma's job.

Can you fix the proof? Not in step 3, unfortunately. If Mr. Pumping Lemma picks $x={\tt 0}^{n-1}$ and $y={\tt 0}$ and $z={\tt 1}^{n-1}$, he followed the rules. But then even if you pick $r=0$ in step 4, it doesn't work: Mr. Pumping Lemma asserts in step 5 that $xy^0z = {\tt 0}^{n-1}{\tt 1}^{n-1}$ is still in the language, and he is right. And if you pick a bigger $r$ in step 4, it is even worse for you.

But you can fix up your proof. You need to make $w$ a little different in step 2. Try fixing it so that when you eliminate $y$ at the end, the part with the ${\tt 0}$'s is too short.

  • $\begingroup$ Now I do understand my mistake, thank you! $\endgroup$ – muffel May 30 '12 at 21:20
  • 1
    $\begingroup$ You are very welcome. I am glad I could help. $\endgroup$ – MJD May 30 '12 at 21:21

Consider proving reverse of language L to be non-regular. Its easy to do. Then using closure property of regular languages(reverse of a regular language is regular) say that since Reverse(L) is not regular therefore L cannot be regular as well.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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