# Math Help - Pumping Lemma

1. ## Pumping Lemma

Hey guys,

Came accross this question today and would greatly appreciate any assistance with it.

Use the Pumping Lemma to prove that language
L
= {0^n1^m : n > m}

is not regular

2. This seems a little tricky. If we try using the simple formulation of Pumping Lemma, then the "pumping segment" may consists of 0's. Multiplying this segment won't lead us to a word that is not in the language.

However, the General version of pumping lemma for regular languages states that a "pumping segment" can be found in every sufficiently long subword. Let's take the number $p$ given by the lemma and consider $0^{p+1}1^p$ (in terms of the theorem, $u=0^{p+1}$, $w=1^p$ and $v=\epsilon$). Then it should be possible to find a nonempty fragment of $w$ that can be iterated, and this would lead us out of the language.

Another way is to use intersection and complement properties of regular languages to reduce the problem to showing that $0^n1^n$ is not regular, where the simple version of the lemma works.

3. Thankyou emakarov. Your help has been great.