title: Does .NET really use NFA for regular expression engine?
body: <p>Article <a href="http://msdn.microsoft.com/en-us/library/e347654k%28v=vs.110%29.aspx" rel="noreferrer">Details of Regular Expression Behavior</a> from MSDN says, that .NET devs decide to use for regular expressions traditional <strong>NFA</strong> engine, because it is faster than <strong>POSIX NFA</strong>, but it is not clear to me, why does this pattern works exponentially slow then?</p>
  
  <pre><code>var regex = new Regex("(a|aa)*b");
  var b = regex.IsMatch("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaac");
  </code></pre>
  
  <p><strong>This simple pattern matching take more than 30 minute to execute</strong>. But if .NET uses traditional NFA, it is possible to simulate it and find match in <strong>O(M*N)</strong> time in the worst case, where M is pattern length and N is text length, which surely is not true in this case. </p>
  
  <p>Article also explains that backtracking is the reason of slow execution, but I still have some questions that can't find answers</p>
  
  <ol>
  <li>What is backtracking? is it only using already matched pattern again like this <code>(a|b)c/1</code>?</li>
  <li>Does traditional <strong>NFA</strong> support backtracking, if no what modification does it need?</li>
  <li>If NFA supports it, but need more slower algorithm to simulate, why .NET can't check if backtracking exist in the pattern, and use one algorithm and use another if it doesn't?</li>
  </ol>