Pumping Lemmas for Parsing
Mathematics Accomplishment | 1968-69
IBM researcher: Alan Cobham
Where the work was done: IBM T.J. Watson Research Center
What we accomplished: In a result often called Cobham's Theorem, Cobham used pumping lemmas to show the limits of what a finite automata could recognize. Later many people used the same techniques to classify what a DFA could deal with. Other uses: The Hartmanis-Stearns problem for a class of tag machines; on the base-dependence of sets of numbers recognizable by finite automata; and uniform tag sequences.
Related links: A. Cobham. On the Base-Dependence of Sets of Numbers Recognizable by Finite Automata, Mathematical Systems Theory, 3:186–192, 1969.
Image credit: Fieldston School (Bronx, NY) yearbook, 1945.