Using the Pumping Lemma

Let’s use the pumping lemma in the form of the demon game to show that the set $$A = \{ {a^n}{b^m}|nm\} $$ is not regular. The set A is the set of strings in a*b* with no more b’s than a’s. The demon, who is betting that A is regular, picks some number k. A good response for you is to pick x = ak, y = bk, and z = ∈. Then xyz =akbk∈A and $$\left| y \right| = k$$ so far you have followed the rules. The demon must now pick u, v, w such that y=uvw and v ≠ ∈. Say the demon picks u, v, w of length j, m, n, respectively, with k= j + m + n and m > 0. No matter what the demon picks, you can take i = 2 and you win: $$xu{\upsilon ^2}\omega z = {a^k}{b^j}{b^m}{b^m}{b^n} = {a^k}{b^{j + 2m + n}} = {a^k}{b^{k + m}}$$ , which is not in A, because the number of b’s is strictly larger than the number of a’s.