Hey guys,

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

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

is not regular

Printable View

- May 5th 2010, 07:47 PMextaticPumping Lemma
Hey guys,

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

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

is not regular

- May 6th 2010, 09:49 AMemakarov
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 $\displaystyle p$ given by the lemma and consider $\displaystyle 0^{p+1}1^p$ (in terms of the theorem, $\displaystyle u=0^{p+1}$, $\displaystyle w=1^p$ and $\displaystyle v=\epsilon$). Then it should be possible to find a nonempty fragment of $\displaystyle 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 $\displaystyle 0^n1^n$ is not regular, where the simple version of the lemma works. - May 6th 2010, 06:34 PMextatic
Thankyou emakarov. Your help has been great.

Is your reponse a sufficient enough answer?? - May 7th 2010, 12:46 AMemakarovQuote:

Thankyou emakarov. Your help has been great.

Quote:

Is your reponse a sufficient enough answer??