A few weeks ago I came across an article describing "A regular expression to check for prime numbers". I was intrigued because processes defined by formal regular languages have an inherently linear runtime while the process described is non-linear. This contradicts the definition of regular languages, specifically the Pumping Lemma. So, how is this even possible? Well, the regular expression discussed in this article and the regex framework it's used with makes clever use of backtracking for realizing this 'magic'. Quite simply, the ...
Read more