Converses of pumping lemmas
Richard Johnsonbaugh, David Miller · 1990
Pumping lemmas appear in courses that study formal languages such as automata theory and the theory of computation.Converses of pumping lemmas, which a.re generally false, are ignored by most of the books tha,t treat formal languages.This is unfortunate since converses of pumping lemmas arise in a natural way and students typically ask whether converses of particular pumping lemmas are true.We give counterexamples to the converse of a pumping lemma for regular langua.gesand to th e converse of Ogden's Lemma, a pumping lemma for context-free languages.We also show tha.t converses to these lemmas are true for languages over a single symbol.We conclude by discussing the counterexa.mple to the converse of Ogden's Lemma with reference to Par&h's necessary condition for a language to be context-free.