Application of Pumping lemma for regular languages 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!
 A: 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:


*

*The defender specifies the pumping length $n$. Think of it as the number of states in the automata that recognizes the language.

*You give the defender a word $w$ from the language that satisfies the condition: $|w| \ge n$.

*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.
A: 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.
A: 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. 
