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
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.
You are welcome.Thankyou emakarov. Your help has been great.
If I understand it right, in this forum people provide ideas that may be helpful, but only you can decide whether you are convinced by them and whether you can convince others (your instructor).Is your reponse a sufficient enough answer??