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

share|improve this question
add comment

3 Answers

up vote 6 down vote accepted

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.

share|improve this answer
    
great explanation - thank you! –  muffel May 30 '12 at 21:20
    
$k=0$ is a possibility often missed. –  Raphael May 31 '12 at 11:00
add comment

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.

share|improve this answer
    
Now I do understand my mistake, thank you! –  muffel May 30 '12 at 21:20
    
You are very welcome. I am glad I could help. –  MJD May 30 '12 at 21:21
add comment

Pumping Lemma for Regular Sets: Let D = (Q,, , q0, F) be a DFA. Let n = |Q|. Let w ∈ L(D) s.t. |w| ≥ n. Then ∃x, y, z ∈ ⋆ s.t. the following all hold: ◮ xyz = w ◮ |xy| ≤ n ◮ |y| > 0, and ◮ ∀k ≥ 0 (xykz ∈ L(D))

of

share|improve this answer
    
This is not an answer to the question asked ... –  martini Oct 22 '13 at 6:32
add comment

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.