Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Regular Expression That Checks If A Number Is Prime

iluxonchik.github.io

Post reply on HN
Print view View original

51–60 of 117 posts

Re: Regular Expression That Checks If A Number Is Prime

#51

Post by Retra »

conistonwater wrote: post #23
jnordwick wrote: post #15

Earlier quoted context omitted.

One of my pet peeves is how PRCE destroyed the definition of "regular" in regular expressions. It has basically made a huge number of programmers illiterate as to what truly is regular in the formal sense.

But why should people care about what is regular in the formal sense ? Rather, regular in this context would mean it can be recognized with a restricted type of algorithm, which resembles the formalism.

They were named "regular" in the formal sense. Thus if they are not regular, it is a misnomer. It would have been just as useful to call them "Perl Matching Expressions", but without all the additional confusion about what a regular expression can do.

Re: Regular Expression That Checks If A Number Is Prime

#52

Post by Chinjut »

jayshua wrote: post #36
Chinjut wrote: post #10

Earlier quoted context omitted.

Sure, for a fixed arbitrary integer M. (Supposing the input is fed in in big-endian order, you just keep track of the remainder modulo M as each new bit comes in, updating it by turning r into (r * 2 + new bit) mod M. Since this only requires finite state, it is regular). But that won't get you a primality checker. You can't get a primality checker. Primes don't comprise a regular language, neither in unary nor in an…

What do you mean by "non trivial base?"

Oh, just as opposed to unary. Writing numbers in the ordinary way in any ordinary base, which is to say, bases greater than 1; base 2, base 3, base ten, whatever.

Re: Regular Expression That Checks If A Number Is Prime

#53

Post by Retra »

db48x wrote: post #39
Chinjut wrote: post #25

Earlier quoted context omitted.

Is there a standard for which additional features one can add on top of regular expressions in the original limited sense and still be considered a regex?

"regular language" is a mathematical term. You can add any features you want to your matcher, but some features allow you to match languages that are not "regular". However, most programmers are not mathematicians or computer scientists, and so are effectively using lay terminology which is similar to but not precisely the same as the mathematical terminology. Most programmers only care that their regex library allow…

The lay definition isn't a definition, per se, it's a misappropriate of the term. Since the lay user only cares about text matching, the term for what they need is "text matching syntax" or some such thing.

And surely you don't think those implementing the regular expression engine are lay people. They should know better.

Re: Regular Expression That Checks If A Number Is Prime

#54

Post by smegel »

conistonwater wrote: post #23
jnordwick wrote: post #15

Earlier quoted context omitted.

One of my pet peeves is how PRCE destroyed the definition of "regular" in regular expressions. It has basically made a huge number of programmers illiterate as to what truly is regular in the formal sense.

But why should people care about what is regular in the formal sense ? Rather, regular in this context would mean it can be recognized with a restricted type of algorithm, which resembles the formalism.

Maybe we should stop talking about regular expressions and talk about pattern matching instead...

Re: Regular Expression That Checks If A Number Is Prime

#55

Post by greydius »

db48x wrote: post #39
Chinjut wrote: post #25

Earlier quoted context omitted.

Is there a standard for which additional features one can add on top of regular expressions in the original limited sense and still be considered a regex?

"regular language" is a mathematical term. You can add any features you want to your matcher, but some features allow you to match languages that are not "regular". However, most programmers are not mathematicians or computer scientists, and so are effectively using lay terminology which is similar to but not precisely the same as the mathematical terminology. Most programmers only care that their regex library allow…

I don't buy the layman argument. Programmers might not be mathematicians or computer scientists, but they should be professionals and held to the same standards as professionals in other fields. For example, a mechanical engineer doesn't use a "laymen" definition of tensile strength when choosing materials for a design.

Re: Regular Expression That Checks If A Number Is Prime

#56

Post by jdnier »

TimWolla wrote: post #3

It should be noted that this is not possible with regular expressions in the traditional sense (i.e. regular expressions only matching regular languages): http://math.stackexchange.com/a/181233/21405 Because of back references PCRE regular expressions can match non-regular languages as well.

For some great exposition on what "regular" actually means, check out http://nikic.github.io/2012/06/15/The-true-power-of-regular-...

"Thus the question arises: Can regular expressions match only regular grammars, or can they also match more? The answer to this is both yes and no"...

Re: Regular Expression That Checks If A Number Is Prime

#58

Post by [deleted] »

jnordwick wrote: post #15
TimWolla wrote: post #3

It should be noted that this is not possible with regular expressions in the traditional sense (i.e. regular expressions only matching regular languages): http://math.stackexchange.com/a/181233/21405 Because of back references PCRE regular expressions can match non-regular languages as well.

One of my pet peeves is how PRCE destroyed the definition of "regular" in regular expressions. It has basically made a huge number of programmers illiterate as to what truly is regular in the formal sense.

[deleted]
Post reply on HN