Do you have more background on that?  As far as I know, burntsushi is entirely correct, NFAs take a constant amount of space to run, and a linear amount of time (all in relation to the length of the input text).<p>Of course, backreferences and other stuff take you out of the realm of regular languages.  Avoid these.