title: How do regex engines account for irregularity?
body: <p>My C is a bit shaky, but I've looked at python's source code and it looks like most of python's <code>re</code> module is implemented by state machines. This comes as no surprise since regular expressions can be reduced to deterministic finite state machines.</p>
  
  <p>I imagine other regex implementations are similar. But few, if any, modern regex implementations are regular according to the textbook definition. Then how do they account for irregularity, like backreferences?</p>
  
  <pre><code>(.*)\1   // this is not regular
  </code></pre>