Okay, so I did some more work on my regex engine, and I worked out how to add counters. Unfortunately, this means that every state now has storage of 2 + max_counter_depth, but I really don't think there's a way arround this. The program is available as nfa2.py and a sample run is available as out2.txt.