“A Lesson in What Not To Do” – Ullman Explains His Work on Automata Theory with Hopcroft

Added: 2026-06-03

[00:00:01]there was a a sense, okay, finite automata really interesting. You use them in in lexical analyzers and they they model uh simple protocols of of all sorts and and and context-free grammars, languages are obviously important in in in parsing.

[00:00:20]Uh so, let's look at all other let's try to invent other kinds of automata.

[00:00:29]Uh and and see what they can do.

[00:00:32]And that turned out to actually be a a misguided approach. What we were really looking at was structure of or- organization of a of a program. So, for example, we looked at stack automata, which was an an idea that um Seymour Ginsburg had had had where uh uh you know, the no- normal parsers were was a pushdown automaton in the sense that you have a stack. You know, that that you just operate move you know, inserting and deleting at the top of of the stack.

[00:01:12]Hopcroft and I we we proved some very very complicated, or at least for the time complicated, facts about what kind of languages you could you could recognize uh if a in using that ar- architecture, but thing is, you don't pay for organization.

[00:01:36]You pay for time, you pay for space.

[00:01:40]Okay.

[00:01:40]And that's why all of the all of the you know, questions about can this kind of automaton recognize this language or do this uh you know, implement this this solve this problem turn out to be irrelevant.

[00:01:56]The only questions that are really interesting are how much time and how much space does it take to solve a problem.

[00:02:03]Okay.

[00:02:04]Um That's That's one of the great lessons, I think, that I that I I I learned about what not to do.

[00:02:14]What did we know at the time? All right.

[00:02:16]We uh um uh You know, it it it seemed like interesting questions, so we we asked them and tried to answer them.