Need to prove language L = {a^nb^m: n < m < 2m} is not regular

Question

I don't understand the pumping lemma very well, and could use a simple break down of how to prove something like this.

Answer 1

Assume that the language L = {a^n b^m: n < m < 2m} is regular. Then, by the pumping lemma, every string in L of length at least p can be written as xyz where |xy| < p, |y| > 0 and for every natural number k, x(y^k)z is also a string in L. Consider the string a^p b^(p+1). This string has length at least p and is in L. Now we consider options for the substring y:

1. y consists only of a's. Then, we can choose k > 1 to increase the number of a's to be greater than the number of b's, getting a string not in L.
2. y consists of both a's and b's. Then, for k > 1, pumping will cause some a's to come after some b's, resulting in a string that can't possibly be in L.
3. y consists only of b's. Then, we can choose k = p so there are at least 2p + 1 b's, giving more than twice the number of b's as there are a's, and therefore a string not in L.

Because these three ways are the only ways to choose the substring y, there is no way to choose y so that the conditions of the pumping lemma are satisfied. This is a contradiction. Therefore, the assumption that the language is regular must be incorrect. It follows that the language is not regular. The proof was by contradiction / reduction ad absurdum.