Most of the regex engines in languages (like Perl) allow keeping track of state by using back references. If you're talking about this, then theoretically, the

Most of the regex engines in languages (like Perl) allow keeping track of state by using back references. If you're talking about this, then theoretically, they aren't "finite state" machines.