EXAMPLE $4\mathrm{.}10$

The language

$L=\{(ab{)}^n{a}^k$:$n>k,k0\}$

is not regular.

Given $m,$ we pick as our string

$w=(ab{)}^{m+1}{a}^m,$

which is in $L.$ Because of the constraint $|xy|m,$ both $x$ and $y$ must be in the part of the string made up of $ab\text{'}$s$.$ The choice of $x$ does not affect the argument, so let us see what can be done with $y.$ If our opponent picks $y=a,$ we choose $i=0$ and get a string not in $L((ab{)}^{**}{a}^{**}).$ If the opponent picks $y=ab,$ we can choose $i=0$ again. Now we get the string $(ab{)}^m{a}^m,$ which is not in $L.$ In the same way, we can deal with any possible choice by the opponent, thereby proving our claim.