# 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.

BACK TO IBM RESEARCH ACCOMPLISHMENTS