Actually, this is false. A lot of regex implementations use a backtracking approach in all cases, causing pathological behavior even on regexes which match a regular language (and so should never take any significant amount of time to process).<p>See <a href="https:&#x2F;&#x2F;swtch.com&#x2F;~rsc&#x2F;regexp&#x2F;regexp1.html" rel="nofollow">https:&#x2F;&#x2F;swtch.com&#x2F;~rsc&#x2F;regexp&#x2F;regexp1.html</a>, which gives<p>a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa<p>(see the backtracking? me neither) as an example.