For this language prove that it is regular or not regularSol

For this language,

prove that it is regular or not regular

Solution

Let us assume the pumping length is p. s = 0^(p^2) 1^p, this satifies the condition m>=n^2. According to pumping lemma this can be divided in to xyz, such that

|xy|<=p, |y|>=0 and xy^iz(i>=0) belongs to L. As |xy|<=p, y will of the form 0^j for 0<j<=p. So xy^0z will be 0^q 1^p,

q = p^2 - j < p^2 so q < p^2 therefore it does not belong to L. So the language is not regular.