The exercise was to write a regex parser. He asked me about worst-case behavior, which is an exponential number of states. He asked for a regex with worst-case behavior, which I could provide, mentioning that I knew this because the textbook I used for the project pointed it out. Behold, a worst-case regex template:

    (a|b)*a(a|b)^n

This requires at least 2^n states in the DFA.

He asked me to prove that 2^n states were required while he waited. I didn't know the proof and wasn't comfortable trying to produce it while being watched. There's no upper limit to how long producing a proof might take.