That's deterministic finite state machines (DFA); the nondeterministic (NFA) representation is linear in regex length (unless you use "a{99}", but that's nonstandard for a reason). You can also do concat/intersect/etc directly on the (actually-regular) regex representaion directly, although it is a bit ugly.