-
Pumping Lemma
Hello i am trying to do this exercise of the pumping lemma and i have no idea how to do it need help please.
The exersice is the following:
Use the pumping lemma to prove that the following language is not regular.
L{a^kb^n : k>=2n, and k,n>=0}
Thanks in advance
-
Re: Pumping Lemma
In this case, one has not to add extra characters (since adding extra a's produces strings still in the language), but remove a nonempty substring of a's. Recall that the pumping lemma says that a sufficiently long string w can be written as w = xyz so that |y| >= 1 and xyiz is in the language for all natural numbers i including 0.
If you need more hints, see here (PPT) or p. 5 here (PDF).