Yes, indeed: I figured this out for myself in the followup post!

Thanks for the link to the Antimirov stuff! One reason I like the Brzozowski implementation more than the Antimirov one is that you can build an implicit-state DFA matcher with just a left fold. Stephanie Weirich did this in a fancily typed way at her POPL 2017 keynote.

If you don’t do any normalization, then Brzozowski derivatives can grow exponentially Consider the regular expression a*.a**, and then take its derivative with respect to a

d_a(a*.a**) = d_a(a*).a** + d_a(a**)
= a*.a** + d_a(a*).a**
= a*.a** + a*.a**

This regular expression has doubled in size, and each derivative with respect to a will double it again.

However, Brzozowski proved in his original paper that if you quotient derivatives by “similarity” (basically ACU with respect to +, but only at the outermost level), then there are only a finite number of word derivatives. So a smart constructor implementation smart enough to ensure that (alt r r == r), (alt r1 r2 == alt r2 r1) and (alt (alt r1 r2) r3 == alt r1 (alt r2 r3)) suffices to ensure you only ever build a finite number of states!

I found the proof in his original paper very obscure, though, and didn’t understand it until I read Antimirov’s paper on partial derivatives. That yields an even simpler implementation technique than Brzozowski’s original — you can use it to implement a complete table-driven DFA-based matcher in ~50 lines of code. See

https://semantic-domain.blogspot.com/2013/11/antimirov-derivatives-for-regular.html