[Overview] [Previous] [Next]
If L is an infinite regular language, then there exists some positive integer m such that any string w L whose length is m or greater can be decomposed into three parts, xyz, where
Let L be an infinite context-free language. Then there is some positive integer m such that, if S is a string of L of length at least m, then
for all nonnegative values of i.
Pumping lemmas are used to show that a given language is not of type (regular/context-free). The argument goes:
Copyright © 1996 by David Matuszek
Last modified Apr 24, 1996