>"Also, there was a request to derive a formal proof while Ammon watched"
You were asked to drive a formal proof? Why exactly? How often is that asked at an actual tech interview?
You were asked to drive a formal proof? Why exactly? How often is that asked at an actual tech interview?
(a|b)*a(a|b)^n
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.
Out of curiosity what book is that DFA problem from?
That proof isn't a problem in the book; it's mentioned, with a hint for those inclined to derive it themselves, in the running text.