- We don't know m, but assume there is one.
- Choose a string w = a
^{n}b^{n}where n > m, so that any prefix of length m consists entirely of a's. - We don't know the decomposition of w into xyz, but since |xy|
m, xy must consist entirely of a's. Moreover, y cannot be empty.
- Choose i = 0. This has the effect of dropping |y| a's out of the string, without affecting the number of b's. The resultant string has fewer a's than b's, hence does not belong to L. Therefore L is not regular.

Copyright © 1996 by David Matuszek

Last modified Feb 18, 1996