3 ms·
I do dislike people calling that expression a "regex", because it isn't: regular expressions cannot contain backreferences, and must be computable in linear tim
by lubutu 14y ago
I do dislike people calling that expression a "regex", because it isn't: regular expressions cannot contain backreferences, and must be computable in linear time, whereas primality tests are polynomial.
- boyter 14y agoWhile I agree I believe this comment by _delirium sums this up rather well, http://news.ycombinator.com/item?id=1486502 http://news.ycombinator.com/item?id=1486502 full comment thread here http://news.ycombinator.com/item?id=1486158 http://news.ycombinator.com/item?id=1486158
- lubutu 14y agoI agree more with philh's response that there is no alternative term for the true meaning of "regular expression" — a regular language, as suggested by _delirium, is not the same thing. I suppose I could accept "regex" as not being a regular expression as such, but the two are used so interchangeably that maintaining a distinction isn't very realistic. I'd personally rather a regular expression described a regular language, and "PCRE" (or so) used for the Turing-complete expressions with a similar syntax.
- baddox 14y agoI'm not a big fan of your explanation. To be more precise, true "regular expressions" are computationally equivalent to deterministic finite automata, which indeed can test an n-character string in O(n) time.
- deleted 14y ago[deleted]
- MileyCyrax 14y agoNFAs and DFAs both recognise the regular languages (and only them).
- laumars 14y agoIt's PCRE (Perl Compatible Regular Expressions) which is one of the most popular dialects of regex. But AFAIK there's isn't a hard and fast RegEx standard. So I'd argue that code is RegEx. I guess it's just a matter of perspective though.